Advertisement
Guest User

Untitled

a guest
Jun 17th, 2019
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.94 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #include <string>
  4. #include <algorithm>
  5. #include <cstring>
  6. using namespace std;
  7. int n;
  8. string s;
  9. int ans;
  10.  
  11. int cal[9999][4][4][4][4];
  12. bool caltrue[9999][4][4][4][4];// initialized as false
  13.  
  14. bool bb[4];
  15. int score(int a=1, int b=1, int c=2) {
  16.     memset(bb, false, sizeof(bb));
  17.     bb[a] = true;
  18.     bb[b] = true;
  19.     bb[c] = true;
  20.     int res = 0;
  21.     for (int i = 1; i <= 3; ++i) res += bb[i];
  22.     return res;
  23.     // return __builtin_popcount(((1 << a) | (1 << b) | (1 << c)) >> 1);
  24. }
  25.  
  26. int dp(int f, char a, char b, char c, char d){
  27.     if (f >= n) return 0;
  28.    
  29.     if(caltrue[f][a][b][c][d]) return cal[f][a][b][c][d];
  30.  
  31.     // if(score(a, b, s[f])>score(c, d, s[f])
  32.    
  33.     int x = dp(f + 1, s[f], a, c, d) + score(a, b, s[f]);
  34.     int y = dp(f + 1, a, b, s[f], c) + score(c, d, s[f]);
  35.    
  36.     caltrue[f][a][b][c][d]=true;
  37.     if (x > y){
  38.         cal[f][a][b][c][d]=x;
  39.         return x;
  40.     }
  41.     else {
  42.         cal[f][a][b][c][d]=y;
  43.         return y;
  44.     }
  45.  
  46. }
  47.      
  48.  
  49. int main() {
  50.     cin >> n >>s;
  51.     for (int i = 0; i < n; ++i) {
  52.         if (s[i] == 'M') s[i] = 1;
  53.         if (s[i] == 'F') s[i] = 2;
  54.         if (s[i] == 'B') s[i] = 3;
  55.     }
  56.     for (int f = n - 1; f >= 0; --f) {
  57.         for (int a = 0; a <= 3; ++a) {
  58.             for (int b = 0; b <= 3; ++b) {
  59.                 for (int c = 0; c <= 3; ++c) {
  60.                     for (int d = 0; d <= 3; ++d) {
  61.                         int x = cal[(f + 1) % 2][s[f]][a][c][d] + score(a, b, s[f]);
  62.                         int y = cal[(f + 1) % 2][a][b][s[f]][c] + score(c, d, s[f]);
  63.                        
  64.                         cal[f % 2][a][b][c][d] = max(x, y);
  65.                         /* int x = dp(f + 1, s[f], a, c, d) + score(a, b, s[f]);
  66.                         int y = dp(f + 1, a, b, s[f], c) + score(c, d, s[f]); */
  67.                     }
  68.                 }
  69.             }
  70.         }
  71.     }
  72.     cout << cal[0][0][0][0][0];
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement