Josif_tepe

Untitled

Dec 17th, 2025
21
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.23 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. int dp[maxn][4][4][4][4];
  13.  
  14. int score(int a, int b, int c) {
  15.     set<int> st;
  16.     if(a != 4) {
  17.         st.insert(a);
  18.     }
  19.     if(b != 4) {
  20.         st.insert(b);
  21.     }
  22.     if(c != 4) {
  23.         st.insert(c);
  24.     }
  25.      
  26.     return (int) st.size();
  27. }
  28. int color(char c) {
  29.     if(c == 'R') return 0;
  30.     if(c == 'G') return 1;
  31.     return 2;
  32. }
  33. int rec(int at, int L1, int L2, int R1, int R2) {
  34.     if(at == n) {
  35.         return 0;
  36.     }
  37.     if(dp[at][L1][L2][R1][R2] != -1) {
  38.         return dp[at][L1][L2][R1][R2];
  39.     }
  40.     int res = -INF;
  41.     int score_left = score(L1, L2, color(s[at]));
  42.     res = max(res, rec(at + 1, L2, color(s[at]), R1, R2) + score_left);
  43.      
  44.     int score_right = score(R1, R2, color(s[at]));
  45.     res = max(res, rec(at + 1, L1, L2, R2, color(s[at])) + score_right);
  46.      
  47.     dp[at][L1][L2][R1][R2] = res;
  48.     return res;
  49. }
  50.  
  51. int main() {
  52.     ios_base::sync_with_stdio(false);
  53.     cin >> n >> s;
  54.     memset(dp, -1, sizeof dp);
  55.      
  56.     cout << rec(0, 4, 4, 4, 4) << endl;
  57.      
  58.      
  59.     return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment