Advertisement
Josif_tepe

Untitled

Feb 9th, 2022
673
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.41 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. int dp[50000][4][4][4][4];
  5.  
  6. int main()
  7. {
  8.     int n;
  9.     cin >> n;
  10.     string s;
  11.     cin >> s;
  12.     for(int i = 0; i < n; i++) {
  13.         for(int j = 0; j < 4; j++) {
  14.             for(int k = 0; k < 4; k++) {
  15.                 for(int x = 0; x < 4; x++) {
  16.                     for(int y = 0; y < 4; y++) {
  17.                         dp[i][j][k][x][y] = -2e9;
  18.                     }
  19.                 }
  20.             }
  21.         }
  22.     }
  23.     dp[0][0][0][0][0] = 0;
  24.     int color = 0;
  25.     int cost;
  26.     for(int i = 0; i < n; i++) {
  27.         for(int l1 = 0; l1 < 4; l1++) {
  28.             for(int l2 = 0; l2 < 4; l2++) {
  29.                 for(int r1 = 0; r1 < 4; r1++) {
  30.                     for(int r2 = 0; r2 < 4; r2++) {
  31.                         vector<bool> visited(4, false);
  32.                         if(s[i] == 'R') color = 1;
  33.                         if(s[i] == 'Y') color = 2;
  34.                         if(s[i] == 'G') color = 3;
  35.                         visited[color] = true;
  36.                         visited[l1] = true;
  37.                         visited[l2] = true;
  38.                         cost = visited[1] + visited[2] + visited[3];
  39.                         dp[i + 1][color][l1][r1][r2] = max(dp[i + 1][color][l1][r1][r2],
  40.                                                            dp[i][l1][l2][r1][r2] + cost);
  41.                         visited[1] = false;
  42.                         visited[2] = false;
  43.                         visited[3] = false;
  44.                         visited[color] = true;
  45.                         visited[r1] = true;
  46.                         visited[r2] = true;
  47.                         cost = visited[1] + visited[2] + visited[3];
  48.                         dp[i + 1][l1][l2][color][r1] = max(dp[i + 1][l1][l2][color][r1],
  49.                                                            dp[i][l1][l2][r1][r2] + cost);
  50.                        
  51.                        
  52.                     }
  53.                 }
  54.             }
  55.         }
  56.     }
  57.     int result = 0;
  58.    
  59.     for(int i = 0; i <= n; i++) {
  60.         for(int j = 0; j < 4; j++) {
  61.             for(int k = 0; k < 4; k++) {
  62.                 for(int x = 0; x < 4; x++) {
  63.                     for(int y = 0; y < 4; y++) {
  64.                         result = max(result, dp[i][j][k][x][y]);
  65.                     }
  66.                 }
  67.             }
  68.         }
  69.     }
  70.     cout << result << endl;
  71.     return 0;
  72. }
  73.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement