HAOI2010 最长公共子序列

wjh15101051's space

卧薪尝胆，厚积薄发。

HAOI2010 最长公共子序列

Date: Thu Sep 13 10:48:21 CST 2018

In Category: NoCategory

Description：

最长公共子序列长度及个数。

$1\le n,m\le 5000$

Solution：

第一问很简单，对于第二问，开一个数组 $g[i][j]$ 表示到 $i,j$ 最长公共子序列个数（可以不包括 $i,j$ ）

若 $c1[i]=c2[j]$

　　 $g[i][j]$ 需加上 $g[i-1][j-1]$

　　注意此时如果 $f[i][j]==f[i-1][j]$ 或 $f[i][j]==f[i][j-1]$ ， $g$ 也应相应累加

若 $c1[i]\ne c2[j]$

　　这时又要分条件，若 $f[i-1][j]\ne f[i][j-1]$

　　 $g$ 即为相应来源的值

　　若二者相等，他们都可以转移过来，都应累加，但这时可能会算重，需简单容斥，若 $f[i-1][j-1]==f[i-1][j]==f[i][j-1]$ ，就减掉公共部分 $g[i-1][j-1]$ 即可

要用滚动数组。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

#define MOD 100000000

using namespace std;

long long ans1 = 0,ans2 = 0;

int f[2][5001];

long long g[2][5001];

int n = 0,m = 0;

char c1[5001],c2[5001];

int main()

{

	char c = getchar();

	while(c < 'A' || c > 'Z')c = getchar();

	while(c >= 'A' && c <= 'Z'){c1[++n] = c;c = getchar();}

	c = getchar();

	while(c < 'A' || c > 'Z')c = getchar();

	while(c >= 'A' && c <= 'Z'){c2[++m] = c;c = getchar();}

	memset(f,0,sizeof(f));

	int cur = 0;

	g[0][0] = 1;

	for(int i = 1;i <= n;++i)g[i&1][0] = 1;

	for(int j = 1;j <= m;++j)g[0][j] = 1;

	for(int i = 1;i <= n;++i)

	{

		cur = i & 1;

		memset(f[cur],0,sizeof(f[cur]));

		memset(g[cur],0,sizeof(g[cur]));

		g[0][0] = g[1][0] = 1;

		for(int j = 1;j <= m;++j)

		{

			if(c1[i] == c2[j])

			{

				f[cur][j] = f[cur^1][j-1] + 1;

				g[cur][j] = g[cur^1][j-1];

				if(f[cur^1][j] == f[cur][j])g[cur][j] += g[cur^1][j];

				if(f[cur][j-1] == f[cur][j])g[cur][j] += g[cur][j-1];

				g[cur][j] %= MOD;

			}

			else

			{

				if(f[cur^1][j] > f[cur][j-1])

				{

					f[cur][j] = f[cur^1][j];

					g[cur][j] = g[cur^1][j];

				}

				if(f[cur^1][j] < f[cur][j-1])

				{

					f[cur][j] = f[cur][j-1];

					g[cur][j] = g[cur][j-1];

				}

				if(f[cur^1][j] == f[cur][j-1])

				{

					f[cur][j] = f[cur^1][j];

					g[cur][j] += g[cur][j-1];

					g[cur][j] += g[cur^1][j];

					if(f[cur^1][j-1] == f[cur][j])g[cur][j] -= g[cur^1][j-1];

				}

				g[cur][j] %= MOD;

			}//cout << i << " " << j << " " << f[i][j] << " " << g[i][j] << endl;

		}

	}

	cout << f[cur][m] << endl << g[cur][m] << endl;

	return 0;

}

In tag: DP-LCS DP-计数DP

wjh15101051