Josif_tepe

Untitled

Dec 17th, 2025
18
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.22 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 main() {
  28.     ios_base::sync_with_stdio(false);
  29.     cin >> n >> s;
  30.     int dp[n + 1][4][4][4][4];
  31.  
  32.     for(int i = 0; i <= n; i++) {
  33.         for(int L1 = 0; L1 <= 3; L1++) {
  34.             for(int L2 = 0; L2 <= 3; L2++) {
  35.                 for(int R1 = 0; R1 <= 3; R1++) {
  36.                     for(int R2 = 0; R2 <= 3; R2++) {
  37.                         dp[i][L1][L2][R1][R2] = -INF;
  38.                     }
  39.                 }
  40.             }
  41.         }
  42.     }
  43.    
  44.    
  45.     dp[0][0][0][0][0] = 0;
  46.    
  47.     int res = 0;
  48.     for(int at = 0; at < n; at++) {
  49.         for(int L1 = 0; L1 <= 3; L1++) {
  50.             for(int L2 = 0; L2 <= 3; L2++) {
  51.                 for(int R1 = 0; R1 <= 3; R1++) {
  52.                     for(int R2 = 0; R2 <= 3; R2++) {
  53.                         int now = at;
  54.                         int next = at + 1;
  55.                        
  56.                         int colour = color(s[at]);
  57.                         int cost = score(L1, L2, colour);
  58.                         dp[next][colour][L1][R1][R2] = max(dp[now][L1][L2][R1][R2] + cost, dp[next][colour][L1][R1][R2]);
  59.                        
  60.                         cost = score(R1, R2, colour);
  61.                         dp[next][L1][L2][colour][R1] = max(dp[now][L1][L2][R1][R2] + cost, dp[next][L1][L2][colour][R1]);
  62.                        
  63.                        
  64.                     }
  65.                 }
  66.             }
  67.         }
  68.     }
  69.      
  70.     for(int L1 = 0; L1 <= 3; L1++) {
  71.         for(int L2 = 0; L2 <= 3; L2++) {
  72.             for(int R1 = 0; R1 <= 3; R1++) {
  73.                 for(int R2 = 0; R2 <= 3; R2++) {
  74.                     res = max(res, dp[n][L1][L2][R1][R2]);
  75.                 }
  76.             }
  77.         }
  78.     }
  79.      
  80.     cout << res << endl;
  81.     return 0;
  82. }
  83.  
Advertisement
Add Comment
Please, Sign In to add comment