https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1825

好久之前的坑.今天想了一下,忽然发现了一个简单做法.

记两个串为$a,b$,长度为$n,m$

设$dp[i][j]$表示$a_{1..i}$和$b_{1..j}$的$lcs$

考虑从$1$到$m$枚举$h$,动态维护无视$b_{1..h}$的$dp$数组(也就是$dp[i][j]$表示$a_{1..i}$和$b_{h+1..j}$的$lcs$)

假如现在枚举到$h$,对于$h$这一列,第一个变化的$dp[i][h]$必定满足$a[i]==b[h]$,并且$dp[i..n][h]$全部会减$1$.

再依次考虑列$h+1,..m$的变化,可以发现每一列变化的都是一个后缀,并且不长于前一列.

所以枚举每一列,维护后缀长度即可.

现在唯一的问题就是判断一个点可以从哪里转移过来.

每次变化的转移边只有轮廓上那些,所以可以轻松维护.

时间$O(n^2)$

(然而被卡常了...不是很懂为什么$n^2$要出成$5000$)

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

template <typename T> void chmin(T&x,const T &y)
{
    if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}
typedef long long s64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef pair<int,int> pii;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define rep0(i,l,r) for(int i=l;i<r;++i)
#define gc (c=getchar())
int read()
{
    char c;
    while(gc<'-');
    if(c=='-')
    {
        int x=gc-'0';
        while(gc>='0')x=x*10+c-'0';
        return -x;
    }
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}
#undef gc

const int N=5000+5,D=998244353;
bool fr[N][N][3];
char s1[N],s2[N];
int dp[N][N],dpn[N];

int main()
{
#ifdef kcz
    freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
#endif
    scanf("%s%s",s1+1,s2+1);
    int n=strlen(s1+1),m=strlen(s2+1);
    rep(i,1,n)
    rep(j,1,m)
    {
        int a=dp[i][j-1],b=dp[i-1][j-1]+(s1[i]==s2[j]),c=dp[i-1][j];
        dp[i][j]=max(max(a,b),c);
        fr[i][j][0]=a==dp[i][j];
        fr[i][j][1]=b==dp[i][j];
        fr[i][j][2]=c==dp[i][j];
    }
    rep(j,1,m)dpn[j]=dp[n][j];
    s64 ans=0;
    rep(h,1,m)
    {
        rep(j,h,m)ans=(ans*233+dpn[j])%D;
        int i=1;
        while(fr[i][h][0]||fr[i][h][2])++i;
        if(i>n)continue;
        rep(j,h+1,m)
        {
            if(!fr[i][j][1]&&!fr[i][j][2])fr[i][j][1]=fr[i][j][2]=1;
            else
            {
                fr[i][j][0]=0;
                while(++i,fr[i][j][2])fr[i][j][0]=fr[i][j][1]=0;
                if(i>n)break;
                fr[i][j][2]=1;
            }
            --dpn[j];
        }
    }
    cout<<ans;
}