这题我真地想了好久怎么构造dp，可惜，最后还是不会构造，真的是太弱了。。。
先来个简单方法，我们用dp[i][a][b][c]表示前i位最长优胜序列的末尾为0的最长长度为a，末尾为1最长长度为b,末尾为2最长长度是c，的方案数。(我觉得给我多久我都根本想不到这种方程的。。。)
那么如果当前第i位可能为0的话dp[i+1][max(a,c+1)][b][c]就加上dp[i][a][b][c];其他的情况也是一样。然而复杂度为O（n^4），只能过40分。
好了怎么优化呢？我们会发现如果结尾为1的最长长度减1必定是一个结尾为0的优胜序列，所以a>=b-1，同理b>=c-1,c>=a-1;所以说我们可以发现他们之间不会相差大于二
我们只要用数组dp[i][a][d1][d2]来维护就可以了，d1，d2，表示a与b的差，和a与c的差。
计算答案只要往ans[max(a,b,c)]中加入这个dp值就可以了。如果没有我这么懒，可以压缩一下第一维。
希望下次自己能做出dp题。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #define mo 998244353 using namespace std; int dp[2001][2001][5][5],n,ans[2001],p[2001][3]; char s[3]; int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%s",s); for (int j=0;j<strlen(s);j++) p[i][s[j]-'0']=true; } int a,b,c,add,now; dp[0][0][2][2]=1; for (int i=1;i<=n;i++) for (int j=0;j<i;j++) for (int k2=0;k2<5;k2++) for (int k3=0;k3<5;k3++) if (dp[i-1][j][k2][k3]) { a=j;b=j+k2-2;c=j+k3-2; add=dp[i-1][j][k2][k3]; if (p[i][0]) { now=max(a,c+1); dp[i][now][b-now+2][c-now+2]=(dp[i][now][b-now+2][c-now+2]+add)%mo; } if (p[i][1]) { now=max(a+1,b); dp[i][a][now-a+2][c-a+2]=(dp[i][a][now-a+2][c-a+2]+add)%mo; } if (p[i][2]) { now=max(b+1,c); dp[i][a][b-a+2][now-a+2]=(dp[i][a][b-a+2][now-a+2]+add)%mo; } } for (int i=0;i<=n;i++) for (int k2=0;k2<5;k2++) for (int k3=0;k3<5;k3++) if (dp[n][i][k2][k3]) { now=max(max(i,i+k2-2),i+k3-2); ans[now]=(ans[now]+dp[n][i][k2][k3])%mo; } for (int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }