D. Three Religions 题解(dp)

题目链接

题目思路

设\(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;
}