【BZOJ2423】最长公共子序列（动态规划）

【BZOJ2423】最长公共子序列（动态规划）

题面

BZOJ
洛谷

题解

今天考试的时候，神仙出题人(fdf)把这道题目作为一个二合一出了出来，我除了orz还是只会orz。

对于如何(O(n^2))求解最长的长度是很简单的。
设(f[i][j])表示第一个串匹配到了(i)，第二个串匹配到了(j)的最大长度。
那么转移很显然，要么(i)向后挪动一位，要么(j)向后挪动一位，要么(i,j)匹配上了。
也就是(f[i][j]=max(f[i-1][j],f[i][j-1],f[i-1][j-1]+1))，最后一个转移当且仅当(X[i]=Y[j])时才有。

考虑如何统计方案。显然是再记录一个数组(g[i][j])表示到了(f[i][j])时最长长度的方案数。
每次转移的时候如果长度一样则相加。
但是注意一个问题，当转移的时候，发现(f[i-1][j],f[i][j-1],f[i-1][j-1])三者转移是相同的时候，
如果直接统计和的话，那么(f[i-1][j-1])的方案会被重复计算两次，因此需要额外减去。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MOD 100000000
#define ll long long
#define MAX 5005
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
int f[2][MAX],g[2][MAX],n,m;
int ans=0,sum=0;
char s[MAX],w[MAX];
int main()
{
	scanf("%s%s",s+1,w+1);
	n=strlen(s+1)-1;m=strlen(w+1)-1;
	for(int i=0;i<=m;++i)g[0][i]=1;
	for(int i=1,nw=1,pw=0;i<=n;++i,nw^=1,pw^=1)
	{
		memset(f[nw],0,sizeof(f[nw]));
		memset(g[nw],0,sizeof(g[nw]));
		g[nw][0]=1;
		for(int j=1;j<=m;++j)
		{
			if(s[i]==w[j])f[nw][j]=f[pw][j-1]+1,g[nw][j]=g[pw][j-1];
			else f[nw][j]=max(f[nw][j-1],f[pw][j]);
			if(f[nw][j]==f[nw][j-1])add(g[nw][j],g[nw][j-1]);
			if(f[nw][j]==f[pw][j])add(g[nw][j],g[pw][j]);
			if(f[nw][j]==f[pw][j]&&f[nw][j]==f[nw][j-1]&&f[nw][j]==f[pw][j-1])add(g[nw][j],MOD-g[pw][j-1]);
		}
	}
	printf("%d
%d
",f[n&1][m],g[n&1][m]);
	return 0;
}