Josif_tepe

Untitled

Dec 17th, 2025
17
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.28 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <cstring>
  5. #include <set>
  6. using namespace std;
  7. const int maxn = 55000;
  8. const int INF = 2e9;
  9.  
  10. string s;
  11. int n;
  12.  
  13. int score(int a, int b, int c) {
  14.     vector<bool> visited(4, false);
  15.     visited[a] = true;
  16.     visited[b] = true;
  17.     visited[c] = true;
  18.    
  19.     return visited[1] + visited[2] + visited[3];
  20. }
  21. int color(char c) {
  22.     if(c == 'R') return 1;
  23.     if(c == 'G') return 2;
  24.     return 3;
  25. }
  26.  
  27. int dp[2][4][4][4][4];
  28.  
  29. int main() {
  30.     ios_base::sync_with_stdio(false);
  31.     cin >> n >> s;
  32.    
  33.  
  34.     for(int i = 0; i < 2; i++) {
  35.         for(int L1 = 0; L1 <= 3; L1++) {
  36.             for(int L2 = 0; L2 <= 3; L2++) {
  37.                 for(int R1 = 0; R1 <= 3; R1++) {
  38.                     for(int R2 = 0; R2 <= 3; R2++) {
  39.                         dp[i][L1][L2][R1][R2] = -INF;
  40.                     }
  41.                 }
  42.             }
  43.         }
  44.     }
  45.    
  46.    
  47.     dp[0][0][0][0][0] = 0;
  48.    
  49.     int res = 0;
  50.     for(int at = 0; at < n; at++) {
  51.         for(int L1 = 0; L1 <= 3; L1++) {
  52.             for(int L2 = 0; L2 <= 3; L2++) {
  53.                 for(int R1 = 0; R1 <= 3; R1++) {
  54.                     for(int R2 = 0; R2 <= 3; R2++) {
  55.                         int now = at % 2;
  56.                         int next = 1 - now;
  57.                        
  58.                         int colour = color(s[at]);
  59.                         int cost = score(L1, L2, colour);
  60.                         dp[next][colour][L1][R1][R2] = max(dp[now][L1][L2][R1][R2] + cost, dp[next][colour][L1][R1][R2]);
  61.                        
  62.                         cost = score(R1, R2, colour);
  63.                         dp[next][L1][L2][colour][R1] = max(dp[now][L1][L2][R1][R2] + cost, dp[next][L1][L2][colour][R1]);
  64.                        
  65.                        
  66.                     }
  67.                 }
  68.             }
  69.         }
  70.     }
  71.      
  72.     for(int L1 = 0; L1 <= 3; L1++) {
  73.         for(int L2 = 0; L2 <= 3; L2++) {
  74.             for(int R1 = 0; R1 <= 3; R1++) {
  75.                 for(int R2 = 0; R2 <= 3; R2++) {
  76.                     res = max(res, dp[0][L1][L2][R1][R2]);
  77.                     res = max(res, dp[1][L1][L2][R1][R2]);
  78.                 }
  79.             }
  80.         }
  81.     }
  82.      
  83.     cout << res << endl;
  84.     return 0;
  85. }
  86.  
Advertisement
Add Comment
Please, Sign In to add comment