【GDOI2018模拟8.7】最长公共子序列

本文主要是介绍【GDOI2018模拟8.7】最长公共子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

这里写图片描述

Input

输入文件名为lcs.in。
输入文件包含两行字符串，分别表示序列A和B 。

Output

输出文件名为lcs.out。
输出文件包含两行。
第一行为L 。
第二个行为合法的二元组的对数对10^9+7取模的结果

Sample Input

输入1：
abbcc
bc

输入2：
cbbdbb
ccaaddacabdbdce

Sample Output

输出1：
2
4

输出2：
4
19

Data Constraint

对于20%的数据，n,m<=10
对于40%的数据，n,m<=20
对于60%的数据，n,m<=100
对于80%的数据，n,m<=1000
对应100%的数据，n,m<=5000，保证序列只包含小写字母。

Solution

就是求最长公共子序列和数量
设f[i][j]为上面到i,下面到j的最长公共子序列
g[i][j]就是为上面到i,下面到j的最长公共子序列的数量
转移自己推吧，就是f从哪转来，g就从哪转来，注意g要避免算重

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 5010
#define mo 1000000007
#define ll long long
using namespace std;
char s[N],t[N];
int n,m,f[N][N];
ll g[N][N];
int main()
{freopen("lcs.in","r",stdin);freopen("lcs.out","w",stdout);scanf("%s\n",s+1);n=strlen(s+1);scanf("%s\n",t+1);m=strlen(t+1);fo(i,0,max(n,m)) g[i][0]=g[0][i]=1;fo(i,1,n){fo(j,1,m){if(f[i-1][j]==f[i][j-1]) {f[i][j]=f[i-1][j],g[i][j]=(g[i-1][j]+g[i][j-1])%mo;if(f[i-1][j-1]==f[i][j]) g[i][j]=(g[i][j]-g[i-1][j-1]+mo)%mo;}else if(f[i-1][j]>f[i][j-1]) f[i][j]=f[i-1][j],g[i][j]=g[i-1][j];else f[i][j]=f[i][j-1],g[i][j]=g[i][j-1];if(s[i]==t[j]){if(f[i-1][j-1]+1>f[i][j]) f[i][j]=f[i-1][j-1]+1,g[i][j]=g[i-1][j-1];else if(f[i-1][j-1]+1==f[i][j]) g[i][j]=(g[i][j]+g[i-1][j-1])%mo;}if(f[i][j]==0) g[i][j]=1;}}printf("%d\n%lld\n",f[n][m],g[n][m]);
}