CF1149B Three Religions

一道新颖的dp好题

题意：

有三个字符串$s_1,s_2,s_3$和一个主串$s$，每次操作改变一个$s_i$ （插入或删除字符），每次操作完之后问$s$是否可以分成3个子序列正好是$s_1,s_2,s_3$ 。任意时候$|s_i|\leq 250$。

题解：

设f[i][j][k]表示A串匹配到第i个字符，B串匹配到第j个字符，C串匹配到第k个字符时，在模式串中的最短距离，即最左点（串的下标都从1开始）

预处理出nxt[i][c]，表示模式串中，[i,n]区间内，c字符第一次出现的位置

下面是一张cf官方的解释nxt数组的图，它的下标从0开始，也许可以方便理解

初始化$f[i][j][k]=n+1,f[0][0][0]=0$，意思是假设怎样都匹配失败，都不去匹配才能成功

转移方程如下：

${f[i][j][k]=\min\left \{nxt[f[i-1][j][k]+1][s[1][i]],nxt[f[i][j-1][k]+1][s[2][j]],nxt[f[i][j][k-1]+1][s[3][k]] \right \}}$

意思是，尝试从A串中加个字符找后续位置，从B串中加个字符找后续位置,从C串中加个字符找后续位置，从这三个位置中的最左边的一个那转移

对于插入操作，注意到新增加的状态只有 新字符与另外两个串的每个位置 这至多250*250种状态，对于这些新状态重新跑一遍dp即可

对于删除操作，直接减小相应串长即可

对于答案ans=f[len[1]][len[2]][len[3]]，意思就是三个串全部匹配完后，在模式串中的最左点

当ans<=n时，说明是可以在模式串中被匹配完的，输出YES

否则ans=n+1就输出NO

特别注意处理nxt数组时，nxt[n+1][]和nxt[n+2][]都要赋为n+1

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=1e5+5,M=255;
char p[N];
int s[4][M],nxt[N][28],f[M][M][M],n,q,len[4];
/*预处理出nxt[][]数组*/
void init(){
    for(int i=0;i<26;i++) nxt[n+1][i]=nxt[n+2][i]=n+1; //注意这边的[n+2]
    for(int i=n;i;i--)
        for(int j=0;j<26;j++){
            if(p[i]==j+'a') nxt[i][j]=i;
            else nxt[i][j]=nxt[i+1][j];
        }
}

void doit(){
    char ch;cin>>ch;
    int id;read(id);
    if(ch=='+'){
        cin>>ch;
        s[id][++len[id]]=ch-'a';
        for(int i=(id==1?len[1]:0);i<=len[1];i++) //三目表达式部分意思是，如果是这个串被修改，那它只要计算新的一位，否则就都要从头开始
            for(int j=(id==2?len[2]:0);j<=len[2];j++)
                for(int k=(id==3?len[3]:0);k<=len[3];k++){
                    int &now=f[i][j][k];
                    now=n+1; //都先假设不可能
                    if(i) now=min(now,nxt[f[i-1][j][k]+1][s[1][i]]); //A串转移
                    if(j) now=min(now,nxt[f[i][j-1][k]+1][s[2][j]]); //B串转移
                    if(k) now=min(now,nxt[f[i][j][k-1]+1][s[3][k]]); //C串转移
                }
    }
    else{
        len[id]--; //直接删长度
    }
    if(f[len[1]][len[2]][len[3]]<=n) puts("YES"); //最左点在n以内就可行
    else puts("NO");
}

signed main(){
    read(n);read(q);
    scanf("%s",p+1);
    init();
    while(q--) doit();
}
赏

fighter