记录编号	284532	评测结果	AAWWWAAAAA
题目名称	445.[HAOI 2010]最长公共子序列	最终得分	70
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	1.212 s
提交时间	2016-07-18 15:21:14	内存使用	115.08 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
char s1[5010],s2[5010];
int f[5010][5010],g[5010][5010];
int len1,len2;
int MAIN();
int haha=MAIN();
int main(){;}
inline int MAIN(){
#define COGS
#ifdef COGS
	freopen("lcs.in","r",stdin);
	freopen("lcs.out","w",stdout);
#endif
	scanf("%[A-Z]",s1+1);
	scanf("%*[^A-Z]");
	scanf("%[A-Z]",s2+1);
	len1=strlen(s1+1);
	len2=strlen(s2+1);
	f[0][0]=f[0][1]=f[1][0]=0;
	for(int i=1;i<=len1;i++)g[i][0]=1;
	for(int j=1;j<=len2;j++)g[0][j]=1;
	for(int i=1;i<=len1;i++){
		for(int j=1;j<=len2;j++){
			g[i][j]=1;
			if(s1[i]==s2[j]){
				f[i][j]=f[i-1][j-1]+1;
				g[i][j]=g[i-1][j-1];
				if(f[i-1][j]==f[i][j])g[i][j]=(g[i][j]+g[i-1][j])%100000000;
				if(f[i][j-1]==f[i][j])g[i][j]=(g[i][j]+g[i][j-1])%100000000;
			}
			else{
				f[i][j]=max(f[i-1][j],f[i][j-1]);
				if(f[i-1][j]>f[i][j-1])g[i][j]=g[i-1][j];
				else if(f[i-1][j]<f[i][j-1])g[i][j]=g[i][j-1];
				else{
					g[i][j]=0;
					if(f[i-1][j-1]==f[i-1][j])g[i][j]-=g[i-1][j-1];
					g[i][j]+=(g[i-1][j]+g[i][j-1])%100000000;
				}
			}
		}
	}
	return printf("%d\n%d",f[len1][len2],g[len1][len2]);
}