其实就是一个比较简单的$IOI$题。简单$dp$就行，设$5$维$dp$即可
最后在滚动一下，判一下可行性即可。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } const int N=3; int dp[N][4][4][4][4]; int val[100001],A[5]; int calc(int a,int b,int c){ A[1]=a,A[2]=b,A[3]=c;sort(A+1,A+3+1); int res=(A[1]!=0); if(A[2]!=A[1]&&A[2]) res++; if(A[3]!=A[2]&&A[3]) res++; return res; } int maxn; int cur; int main(){ cur=0; memset(dp,-1,sizeof(dp));dp[0][0][0][0][0]=0; int n=read(); for(int i=1;i<=n;i++){char str=getchar();if(str=='M') val[i]=1;if(str=='F')val[i]=2;if(str=='B') val[i]=3;} for(int i=1;i<=n;i++){ cur^=1; for(int t1=0;t1<=3;t1++) for(int t2=0;t2<=3;t2++) for(int t3=0;t3<=3;t3++) for(int t4=0;t4<=3;t4++){ if(dp[cur^1][t1][t2][t3][t4]==-1) continue; dp[cur][t2][val[i]][t3][t4]=max(dp[cur][t2][val[i]][t3][t4],dp[cur^1][t1][t2][t3][t4]+calc(t1,t2,val[i])); dp[cur][t1][t2][t4][val[i]]=max(dp[cur][t1][t2][t4][val[i]],dp[cur^1][t1][t2][t3][t4]+calc(t3,t4,val[i])); } memset(dp[cur^1],-1,sizeof(dp[cur^1])); } for(int t1=0;t1<=3;t1++) for(int t2=0;t2<=3;t2++) for(int t3=0;t3<=3;t3++) for(int t4=0;t4<=3;t4++) if(dp[cur][t1][t2][t3][t4]!=-1)maxn=max(maxn,dp[cur][t1][t2][t3][t4]); cout<<maxn; }