题意

题解

但是我太菜了，所以我是$\mathcal O({16}^2n)$ 的。

调试记录

• 没用滚动数组
•  for (int l=0; l<16; l++) 打成了 for (int l=0; j<16; j++) ...

代码

1 #include 
     
       2 #pragma GCC optimize(3)  3 #define up(x, y) x = max(x, y) 4 using namespace std; 5  6 char a[100005]; 7 int dp[2][16][16]; 8  9 inline int typ(char x) {10     return x == 'M' ? 0 : (x == 'F' ? 1 : (x == 'B' ? 2 : 3));11 }12 inline int sta(int pr, int pe) {13     return pr * 4 + pe;14 }15 inline int E(int sta) {16     return sta % 4;17 }18 inline int R(int sta) {19     return sta / 4;20 }21 int kinds[3];22 inline int cnt(int sta, int x) {23     int r = R(sta), e = E(sta);24     kinds[0] = x; int p=0;25     if (r != 3) kinds[++p] = r;26     if (e != 3) kinds[++p] = e;27     sort(kinds, kinds+p+1);28     int m=1, z=kinds[0];29     for (int i=1; i<=p; i++)30         if (kinds[i] != z) ++m, z = kinds[i];31     return m;32 }33 34 int main() {35     int n; scanf("%d", &n);36     scanf("%s", a+1);37     memset(dp[0], 200, sizeof(dp[0]));38     int cur = 0, nxt = 1;39     dp[cur][sta(3, 3)][sta(3, 3)] = 0;40     for (int i=1; i<=n; i++) {41         memset(dp[nxt], 200, sizeof(dp[nxt]));42         for (int j=0; j<16; j++)43             for (int l=0; l<16; l++) {44                 if (R(j) != 3 && E(j) == 3) continue;45                 if (R(l) != 3 && E(l) == 3) continue;46                 int x = typ(a[i]);47                 up(dp[nxt][sta(E(j), x)][l], dp[cur][j][l] + cnt(j, x));48                 up(dp[nxt][j][sta(E(l), x)], dp[cur][j][l] + cnt(l, x));49             }50         cur = !cur; nxt = !nxt;51     }52     int ans = 0;53     for (int i=0; i<16; i++) for(int j=0; j<16; j++) {54         up(ans, dp[cur][i][j]);55     }56     printf("%d\n", ans);57     return 0;58 }