Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- int dp[50000][4][4][4][4];
- int main()
- {
- int n;
- cin >> n;
- string s;
- cin >> s;
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < 4; j++) {
- for(int k = 0; k < 4; k++) {
- for(int x = 0; x < 4; x++) {
- for(int y = 0; y < 4; y++) {
- dp[i][j][k][x][y] = -2e9;
- }
- }
- }
- }
- }
- dp[0][0][0][0][0] = 0;
- int color = 0;
- int cost;
- for(int i = 0; i < n; i++) {
- for(int l1 = 0; l1 < 4; l1++) {
- for(int l2 = 0; l2 < 4; l2++) {
- for(int r1 = 0; r1 < 4; r1++) {
- for(int r2 = 0; r2 < 4; r2++) {
- vector<bool> visited(4, false);
- if(s[i] == 'R') color = 1;
- if(s[i] == 'Y') color = 2;
- if(s[i] == 'G') color = 3;
- visited[color] = true;
- visited[l1] = true;
- visited[l2] = true;
- cost = visited[1] + visited[2] + visited[3];
- dp[i + 1][color][l1][r1][r2] = max(dp[i + 1][color][l1][r1][r2],
- dp[i][l1][l2][r1][r2] + cost);
- visited[1] = false;
- visited[2] = false;
- visited[3] = false;
- visited[color] = true;
- visited[r1] = true;
- visited[r2] = true;
- cost = visited[1] + visited[2] + visited[3];
- dp[i + 1][l1][l2][color][r1] = max(dp[i + 1][l1][l2][color][r1],
- dp[i][l1][l2][r1][r2] + cost);
- }
- }
- }
- }
- }
- int result = 0;
- for(int i = 0; i <= n; i++) {
- for(int j = 0; j < 4; j++) {
- for(int k = 0; k < 4; k++) {
- for(int x = 0; x < 4; x++) {
- for(int y = 0; y < 4; y++) {
- result = max(result, dp[i][j][k][x][y]);
- }
- }
- }
- }
- }
- cout << result << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement