Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <cstring>
- #include <set>
- using namespace std;
- const int maxn = 55000;
- const int INF = 2e9;
- string s;
- int n;
- int score(int a, int b, int c) {
- vector<bool> visited(4, false);
- visited[a] = true;
- visited[b] = true;
- visited[c] = true;
- return visited[1] + visited[2] + visited[3];
- }
- int color(char c) {
- if(c == 'R') return 1;
- if(c == 'G') return 2;
- return 3;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin >> n >> s;
- int dp[n + 1][4][4][4][4];
- for(int i = 0; i <= n; i++) {
- for(int L1 = 0; L1 <= 3; L1++) {
- for(int L2 = 0; L2 <= 3; L2++) {
- for(int R1 = 0; R1 <= 3; R1++) {
- for(int R2 = 0; R2 <= 3; R2++) {
- dp[i][L1][L2][R1][R2] = -INF;
- }
- }
- }
- }
- }
- dp[0][0][0][0][0] = 0;
- int res = 0;
- for(int at = 0; at < n; at++) {
- for(int L1 = 0; L1 <= 3; L1++) {
- for(int L2 = 0; L2 <= 3; L2++) {
- for(int R1 = 0; R1 <= 3; R1++) {
- for(int R2 = 0; R2 <= 3; R2++) {
- int now = at;
- int next = at + 1;
- int colour = color(s[at]);
- int cost = score(L1, L2, colour);
- dp[next][colour][L1][R1][R2] = max(dp[now][L1][L2][R1][R2] + cost, dp[next][colour][L1][R1][R2]);
- cost = score(R1, R2, colour);
- dp[next][L1][L2][colour][R1] = max(dp[now][L1][L2][R1][R2] + cost, dp[next][L1][L2][colour][R1]);
- }
- }
- }
- }
- }
- for(int L1 = 0; L1 <= 3; L1++) {
- for(int L2 = 0; L2 <= 3; L2++) {
- for(int R1 = 0; R1 <= 3; R1++) {
- for(int R2 = 0; R2 <= 3; R2++) {
- res = max(res, dp[n][L1][L2][R1][R2]);
- }
- }
- }
- }
- cout << res << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment