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;
}
鄂公网安备 42010202000505 号