BZOJ 2423 最长公共子序列

Description

字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1,…,xm-1”,序列Y=“y0,y1,…,yk-1”是X的子序列,存在X的一个严格递增下标序列<i0,i1,…,ik-1>,使得对所有的j=0,1,…,k-1,有xij = yj。例如,X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。对给定的两个字符序列,求出他们最长的公共子序列长度,以及最长公共子序列个数。

Input

第1行为第1个字符序列,都是大写字母组成,以”.”结束。长度小于5000。
第2行为第2个字符序列,都是大写字母组成,以”.”结束,长度小于5000。

Output

第1行输出上述两个最长公共子序列的长度。
第2行输出所有可能出现的最长公共子序列个数,答案可能很大,只要将答案对100,000,000求余即可。
 

Sample Input

ABCBDAB.
BACBBD.

Sample Output

4
7

HINT

首先,求最长子序列就是一个经典的dp了。f[i][j]表示s1到第i位,s2到第j位的最长子序列,f[i][j]=max(f[i-1][j-1]+(s1[i]==s2[j]),f[i-1][j],f[i][j-1])。

麻烦的就是方案的转移,我们另g[i][j]表示s1到第i位,s2到第j位的最长子序列的方案数。考虑以下的几种情况:

1.s1[i]==s2[j],f[i][j]=f[i-1][j-1]+1。g[i][j]=g[i-1][j-1]+(f[i-1][j]==f[i][j])*g[i-1][j]+(f[i][j-1]==f[i][j])*g[i][j-1],三种情况互不包含(g[i-1][j-1]指s1[i]与s2[j]配对;若f[i-1][j]==f[i][j]的话,一定有s1[i-1]与s2[j]配对(否则f不会相等),累加g[i-1][j];同理g[i][j-1]指的是s1[i]与s2[j-1]配对),直接加即可。

2.否则的话,f[i][j]=max(f[i-1][j],f[i][j-1]),若两者相等,则g[i][j]=g[i-1][j]+g[i][j-1]-g[i-1][j-1],因为中间部分两者都计算了一遍,否则就加上大者即可。

由于O(n^2)的空间肯定是开不下的,所以我们要利用滚动数组。

 #include<cstring>
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std; #define rhl (100000000)
#define maxn 5010
char s1[maxn],s2[maxn];
int f[][maxn],g[][maxn],n,m; inline void dp()
{
n = strlen(s1+),m = strlen(s2+);
s1[n--] = s2[m--] = ;
for (int i = ;i <= m;++i) g[][i] = ;
for (int i = ;i <= n;++i)
{
int p = i&,q = p^;
g[p][] = ;
for (int j = ;j <= m;++j)
{
g[p][j] = ;
if (s1[i] == s2[j])
{
f[p][j] = f[q][j-]+;
g[p][j] += g[q][j-];
if (f[q][j] == f[p][j]) g[p][j] += g[q][j];
if (f[p][j-] == f[p][j]) g[p][j] += g[p][j-];
}
else
{
f[p][j] = max(f[p][j-],f[q][j]);
if (f[p][j-] > f[q][j]) g[p][j] = g[p][j-];
else if (f[q][j] > f[p][j-]) g[p][j] = g[q][j];
else
{
g[p][j] = g[q][j]+g[p][j-];
if (f[q][j-] == f[p][j]) g[p][j] -= g[q][j-];
}
}
while (g[p][j] >= rhl) g[p][j] -= rhl;
while (g[p][j] < ) g[p][j] += rhl;
}
}
printf("%d\n%d",f[n&][m],g[n&][m]);
} int main()
{
freopen("2423.in","r",stdin);
freopen("2423.out","w",stdout);
scanf("%s%s",s1+,s2+);
dp();
fclose(stdin); fclose(stdout);
return ;
}
上一篇:sql语句with as 和with(nolock)


下一篇:170222、使用Spring Session和Redis解决分布式Session跨域共享问题