题目链接
题目思路
设\(dp[i][j][k]\)表示匹配了第一个字符串的\(i\)位,第二个字符串的\(j\)位,第三个字符串的第\(k\)位
然后转移即可
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=250+5,inf=0x3f3f3f3f,mod=998244353;
const double eps=1e-6;
int n,q;
char s[100000+5];
char t[5][maxn];
int len[5];
int dp[maxn][maxn][maxn];
int nxt[100000+5][30];
signed main(){
scanf("%d%d",&n,&q);
scanf("%s",s+1);
for(int i=1;i<=26;i++){
nxt[n+1][i]=n+1;
}
for(int i=n;i>=1;i--){
for(int j=1;j<=26;j++){
nxt[i][j]=nxt[i+1][j];
}
nxt[i][s[i]-'a'+1]=i;
}
dp[0][0][0]=0;
for(int i=1,id;i<=q;i++){
char opt,ch;
scanf(" %c %d",&opt,&id);
if(opt=='+'){
scanf(" %c",&ch);
len[id]++;
t[id][len[id]]=ch;
for(int a=(id==1?len[1]:0);a<=len[1];a++){
for(int b=(id==2?len[2]:0);b<=len[2];b++){
for(int c=(id==3?len[3]:0);c<=len[3];c++){
if(a|b|c) dp[a][b][c]=n+1;
if(a&&dp[a-1][b][c]<=n) dp[a][b][c]=min(dp[a][b][c],nxt[dp[a-1][b][c]+1][t[1][a]-'a'+1]);
if(b&&dp[a][b-1][c]<=n) dp[a][b][c]=min(dp[a][b][c],nxt[dp[a][b-1][c]+1][t[2][b]-'a'+1]);
if(c&&dp[a][b][c-1]<=n) dp[a][b][c]=min(dp[a][b][c],nxt[dp[a][b][c-1]+1][t[3][c]-'a'+1]);
}
}
}
}else{
len[id]--;
}
printf(dp[len[1]][len[2]][len[3]]<=n?"YES\n":"NO\n");
}
return 0;
}