[CF1149B] Three Religions – 动态dp

Description

给定长度为 \(n\) 的母串和三个子串 \(s_1,s_2,s_3\)。初始时子串均为空。

有 \(q\) 次询问。你需要支持两种操作：向某个子串末尾添加一个字母，或者删去某个子串末尾的字母。

在每次操作后，你需要回答，是否能从母串中分离出三个不相交的子序列，满足这三个子序列恰好是 \(s_1,s_2,s_3\)。

在任意时刻，\(s_1,s_2,s_3\) 的长度均不会超过 \(250\)。

\(1 \le n \le 10^5\) , \(1\le q \le 10^3\)

Solution

设 \(f[i][j][k]\) 表示三个子串分别匹配到了第 \(i,j,k\) 个字符，在母串中推进的最短距离

设 \(g[i][c]\) 表示 \(S[i..n]\) 内字符 \(c\) 第一次出现的位置

初始条件 \(f[0][0][0]=0\)，其余初值设为 \(+\infty\)

对于插入操作，暴力计算即可，每次 \(O(l^2)\)

对于删除操作，减小串长即可

对于询问，比较 \(f[l_1][l_2][l_3]\) 是否 \(\le n\) 即可

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

char s[N],s1[N],s2[N],s3[N];
int n,l1,l2,l3,q,id,g[N][26],f[255][255][255];
char op,tmp;

void presolve()
{
    for(int i=0;i<26;i++)
    {
        int ch='a'+i;

        vector <int> vec;
        for(int j=1;j<=n;j++) if(s[j]==ch) vec.push_back(j);

        int pos=1;
        for(auto now:vec)
        {
            for(int j=pos;j<=now;j++) g[j][i]=now;
            pos=now+1;
        }
        for(int j=pos;j<=n+2;j++) g[j][i]=n+1;
    }
}

void dp1(int i)
{
    for(int j=0;j<=l2;j++)
    {
        for(int k=0;k<=l3;k++)
        {
            int tmp=1e9;
            if(i) tmp=min(tmp, g[f[i-1][j][k]+1][s1[i]-'a']);
            if(j) tmp=min(tmp, g[f[i][j-1][k]+1][s2[j]-'a']);
            if(k) tmp=min(tmp, g[f[i][j][k-1]+1][s3[k]-'a']);
            f[i][j][k]=tmp;
        }
    }
}

void dp2(int j)
{
    for(int i=0;i<=l1;i++)
    {
        for(int k=0;k<=l3;k++)
        {
            int tmp=1e9;
            if(i) tmp=min(tmp, g[f[i-1][j][k]+1][s1[i]-'a']);
            if(j) tmp=min(tmp, g[f[i][j-1][k]+1][s2[j]-'a']);
            if(k) tmp=min(tmp, g[f[i][j][k-1]+1][s3[k]-'a']);
            f[i][j][k]=tmp;
        }
    }
}

void dp3(int k)
{
    for(int i=0;i<=l1;i++)
    {
        for(int j=0;j<=l2;j++)
        {
            int tmp=1e9;
            if(i) tmp=min(tmp, g[f[i-1][j][k]+1][s1[i]-'a']);
            if(j) tmp=min(tmp, g[f[i][j-1][k]+1][s2[j]-'a']);
            if(k) tmp=min(tmp, g[f[i][j][k-1]+1][s3[k]-'a']);
            f[i][j][k]=tmp;
        }
    }
}

void cl1(int i)
{
    for(int j=0;j<=l2;j++)
    {
        for(int k=0;k<=l3;k++)
        {
            f[i][j][k]=n+1;
        }
    }
}

void cl2(int j)
{
    for(int i=0;i<=l1;i++)
    {
        for(int k=0;k<=l3;k++)
        {
            f[i][j][k]=n+1;
        }
    }
}

void cl3(int k)
{
    for(int i=0;i<=l1;i++)
    {
        for(int j=0;j<=l2;j++)
        {
            f[i][j][k]=n+1;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n>>q>>s+1;

    for(int i=0;i<=254;i++)
    {
        for(int j=0;j<=254;j++)
        {
            for(int k=0;k<=254;k++)
            {
                f[i][j][k]=n+1;
            }
        }
    }

    presolve();

    f[0][0][0]=0;

    for(int i=1;i<=q;i++)
    {
        cin>>op;
        if(op=='+')
        {
            cin>>id>>tmp;
            if(id==1) s1[++l1]=tmp, dp1(l1);
            if(id==2) s2[++l2]=tmp, dp2(l2);
            if(id==3) s3[++l3]=tmp, dp3(l3);
        }
        else
        {
            cin>>id;
            if(id==1) cl1(l1), --l1;
            if(id==2) cl2(l2), --l2;
            if(id==3) cl3(l3), --l3;
        }
        cout<<(f[l1][l2][l3]<=n ? "YES" : "NO")<<endl;
    }
}