[DP][字符串匹配][子序列] codeforces 1150 D Three Religions

vp了这一场，这个D题难到出现断层。。。C过了1k人的时候D没人过，太狠了

主要是能想到用dp搞字符串匹配的。。。div2里这样的人应该不多吧

但是这个题其实内涵里有诱导dp的思想：刚开始没有搞懂他这里的append是什么意思，后来才懂得他每次的+-操作都是在修改对应的religion的描述，这个描述是一个只有小写字母的先后顺序固定的字符串。。然后题目问的就是给定你一个字符串叫做word of universe，问3个religion能不能共存，其实意思就是能不能从这个word of universe分离出来三个subsequence，他们互不相交，又正好是3个religion的描述。

vp的时候毫无头绪，正解里的预处理表倒是想到了也写了但是没用上。确实没想到会是dp emmmm 。既然dp那一定有个数值型的对象吧，他这里就很妙的把问题转化为满足这三个subsequence共存的序列至少要多长了。。。当然给定的word of universe是确定的，这里其实可以认为后面还有无限长的字符串。。。但是长度大于n的时候我们认为没用了。。就输出NO就可以。不得不说确实是很精妙，legendary出的题确实厉害👍

具体地，设dp(n1,n2,n3)为region1满足前n1个字符，region2满足前n2个，region3满足前n3个这样的情况下所需要的在word of universe里的前缀至少有多长。有一个暴力的计算O(250^3)复杂度的，就是

\[
dp\left(n_{1}, n_{2}, n_{3}\right)=\min \left\{\begin{array}{ll}{Nst\left(dp\left(n_{1}-1, n_{2}, n_{3}\right)+1, \text{description}_{1}\left[n_{1}\right]\right)} & {\text { if } n_{1} \geq 1} \\ {Nst\left(dp\left(n_{1}, n_{2}-1, n_{3}\right)+1, \text{description}_{2}\left[n_{2}\right]\right)} & {\text { if } n_{2} \geq 1} \\ {Nst\left(dp\left(n_{1}, n_{2}, n_{3}-1\right)+1, \text { description }_{3}\left[n_{3}\right]\right)} & {\text { if } n_{3} \geq 1}\end{array}\right.
\]

其中nst是一个预处理出来的表，Nst(i,c)表示字符c在i及i之后的word of univers中出现的第一个位置。

当然不可能每次都转移，这样时间复杂度太大，但是从这个递推式可以看出来+一个字符的时候只需要修改n=i这一层，也就是250*250的复杂度，因为即使你之后再+那他也不会造成“突变”，因为字符+-都是一个一个来的。而-的话根本不用操作，只需要改变记录的描述字符串就行了，因为这时候下标变小了，从递推式可以看出来这时候不用进行任何操作,大范围对了那小范围也一定是对的。

wa点和细节主要在于，下标的处理，是0-n-1还是1-n，长度和下标的关系等。

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn=1e5+5;
const int maxm=255;
const ll ub=(ll)100000000000000;

char s[maxn];
string des[4];
int nst[maxn][30];
int dp[maxm][maxm][maxm];

int n,q,r,max1,max2,max3;

void cal(int a,int b,int c){
    int& v=dp[a][b];
    v=n;
    if(a){
        v=min(v,nst[dp[a-1][b]+1][des[1][a-1]-'a']);
    }
    if(b){
        v=min(v,nst[dp[a][b-1]+1][des[2][b-1]-'a']);
    }
    if(c){
        v=min(v,nst[dp[a][b][c-1]+1][des[3][c-1]-'a']);
    }
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    char op,cr;
    cin>>n>>q;
    cin>>s;
    for(int j=0;j<26;j++){
            nst[n][j]=nst[n+1][j]=n;
    }
    for(int i=n-1;i>=0;i--){
        for(int j=0;j<26;j++){
            if(('a'+j)==s[i]) nst[i][j]=i;
            else nst[i][j]=nst[i+1][j];
            //cout<<nst[i][j]<<" ";
        }
        //cout<<endl;
    }
    dp[0][0][0]=-1;//error1
    while(q--){
        cin>>op>>r;
        if(op=='+'){
            cin>>cr;
            des[r]+=cr;
            max1=des[1].length(),max2=des[2].length(),max3=des[3].length();
            max1=des[1].size(),max2=des[2].size(),max3=des[3].size();
            int min1=(r==1?max1:0);
            int min2=(r==2?max2:0);
            int min3=(r==3?max3:0);
            for(int _=min1;_<=max1;_++)
                for(int __=min2;__<=max2;__++)
                    for(int ___=min3;___<=max3;___++)
                        cal(_,__,___);
        }
        else{
            des[r].pop_back();
        }
        //cout<<dp[des[1].size()][des[2].size()][des[3].size()]<<endl;
        if(dp[des[1].size()][des[2].size()][des[3].size()]<n)
            cout<<"YES\n";
        else 
            cout<<"NO\n";
    }

    return 0;
}