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

题面

题解

今天考试的时候，神仙出题人\(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\n%d\n",f[n&1][m],g[n&1][m]);

	return 0;

}

巴特西

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

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

题面

题解

最新文章

热门文章