模板题链接:P2516 HAOI2010最长公共子序列
我们借题解第一篇的巨佬的图
我们\(O(n^2)\)的枚举\(i\),\(j\)(分别对应两个串的下标)
我们记两串分别为\(a,b\),记\(dp[i][j]\)为截止到\(i,j\)时的最长公共子序列,如果\(a[i]==b[j]\)匹配成功,我们可直接用\(dp[i-1][j-1]+1\)来扩展\(dp[i][j]\),相当于在网格图中连一条斜边。若没有斜边,我们就通过\(dp[i-1][j]\)和\(dp[i][j-1]\)取\(max\)来扩展。
对于方案的统计,和上面是同理的,只需注意在\(dp[i-1][j-1]=dp[i][j]\)时,\(dp[i][j-1]\)和\(dp[i-1][j-1]\)由\(dp[i-1][j-1]\)转移来,再分别转移到\(dp[i][j]\),是同一种情况,但是被计数了两次,所以要减掉一份。
代码如下:(加了滚动数组)
#include<bits/stdc++.h>
using namespace std;
#define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
#define LL long long
#define N 5010
#define mods (LL)(1e8)
char a[N],b[N];
LL dp[2][N];
LL cnt[2][N];
inline LL Max(LL x,LL y){
return x>y?x:y;
}
void LCS()
{
bool now=1,last=0;
int lena=strlen(a+1),lenb=strlen(b+1);
//printf("%d %d\n",lena,lenb);
for(int i=0;i<=lenb;++i) cnt[0][i]=1;
cnt[1][0]=1;
for(int i=1;i<=lena;++i,now^=1,last^=1)
{
for(int j=1;j<=lenb;++j)
{
cnt[now][j]=0;
dp[now][j]=((a[i]==b[j])?dp[last][j-1]+1:Max(dp[last][j],dp[now][j-1]));
if(a[i]==b[j]){
cnt[now][j]+=cnt[last][j-1];
}
if(dp[now][j]==dp[now][j-1]){
cnt[now][j]+=cnt[now][j-1];
}
if(dp[now][j]==dp[last][j]){
cnt[now][j]+=cnt[last][j];
}
if(dp[now][j]==dp[last][j-1]){
cnt[now][j]-=cnt[last][j-1];
}
cnt[now][j]%=mods;
}
}
printf("%lld\n%lld",dp[last][lenb],cnt[last][lenb]);
}
int main(){
int top=0;
char ch=getchar();
while(ch!='.') {a[++top]=ch;ch=getchar();}
//cout<<top<<endl;
ch=getchar();
top=0;ch=getchar();
while(ch!='.') {b[++top]=ch;ch=getchar();}
//cout<<top<<endl;
LCS();
return 0;
}