题目设计的很好，感觉做了这题对dp的状态有了更深的理解
/* 先预处理序列自动机 dp[i][j][k]表示匹配到i,j,k时的最靠前的位置 那么现在A串加入了一个字母，我们要求的就是dp[i+1][j][k] 根据dp的状态转移 因为 dp[i][j][k]之前的状态已经全部确定下来， 所以只要在i+1的状态下枚举两重循环jk即可 */ #include<bits/stdc++.h> using namespace std; #define maxn 100005 char s[maxn]; int n,pos[26],q,nxt[maxn][26]; void init(){ for(int i=0;i<26;i++)pos[i]=n+1; for(int i=n;i>=0;i--){ for(int j=0;j<26;j++) nxt[i][j]=pos[j]; pos[s[i]-'a']=i; } for(int i=0;i<26;i++) nxt[n+1][i]=n+1; } int A,B,C,dp[300][300][300]; char a[maxn],b[maxn],c[maxn]; int main(){ scanf("%d%d%s",&n,&q,s+1); init(); char op[2],ch[2];int p; while(q--){ cin>>op>>p; if(op[0]=='-'){ if(p==1)A--;if(p==2)B--;if(p==3)C--; } else { cin>>ch; if(p==1){//带A的所有新状态 a[++A]=ch[0]; for(int j=0;j<=B;j++) for(int k=0;k<=C;k++) dp[A][j][k]=n+1; for(int j=0;j<=B;j++) for(int k=0;k<=C;k++){ dp[A][j][k]=min(dp[A][j][k],nxt[dp[A-1][j][k]][a[A]-'a']); if(j)dp[A][j][k]=min(dp[A][j][k],nxt[dp[A][j-1][k]][b[j]-'a']); if(k)dp[A][j][k]=min(dp[A][j][k],nxt[dp[A][j][k-1]][c[k]-'a']); //cout<<dp[A][j][k]<<' '; } } if(p==2){ b[++B]=ch[0]; for(int i=0;i<=A;i++) for(int k=0;k<=C;k++) dp[i][B][k]=n+1; for(int i=0;i<=A;i++) for(int k=0;k<=C;k++){ dp[i][B][k]=min(dp[i][B][k],nxt[dp[i][B-1][k]][b[B]-'a']); if(i)dp[i][B][k]=min(dp[i][B][k],nxt[dp[i-1][B][k]][a[i]-'a']); if(k)dp[i][B][k]=min(dp[i][B][k],nxt[dp[i][B][k-1]][c[k]-'a']); } } if(p==3){ c[++C]=ch[0]; for(int i=0;i<=A;i++) for(int j=0;j<=B;j++) dp[i][j][C]=n+1; for(int i=0;i<=A;i++) for(int j=0;j<=B;j++){ dp[i][j][C]=min(dp[i][j][C],nxt[dp[i][j][C-1]][c[C]-'a']); if(i)dp[i][j][C]=min(dp[i][j][C],nxt[dp[i-1][j][C]][a[i]-'a']); if(j)dp[i][j][C]=min(dp[i][j][C],nxt[dp[i][j-1][C]][b[j]-'a']); } } } // cout<<dp[A][B][C]<<' '; if(dp[A][B][C]!=n+1)puts("YES"); else puts("NO"); } }