记录编号	244560	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]最长公共子序列	最终得分	100
用户昵称	NewBee	是否通过	通过
代码语言	C++	运行时间	2.665 s
提交时间	2016-04-01 11:13:14	内存使用	191.79 MiB

#include<cstdio>
#include<cstring>
#define Fe freopen("lcs.in","r",stdin);freopen("lcs.out","w",stdout);Init();fclose(stdin);fclose(stdout);return 0;
//designed by New_Beeؼ 
using namespace std;
const int maxn=5010;
int tim=100000000;
int l[maxn][maxn],f[maxn][maxn];
void Init();
int getmax(int,int);
int main(){
	Fe;
}
void Init(){
	memset(l,0,sizeof(l));memset(f,0,sizeof(f));
	char a[maxn],b[maxn];
	int k=1;
	while(scanf("%c",&a[k]),a[k]!='.')k++;
	int lena=k-1;k=1;
	getchar();
	while(scanf("%c",&b[k]),b[k]!='.')k++;
	int lenb=k-1;
	for(int i=0;i<maxn;i++)f[0][i]=f[i][0]=1;
	for(int i=1;i<=lena;i++){
		for(int j=1;j<=lenb;j++){
			if(a[i]!=b[j]){
				l[i][j]=getmax(l[i-1][j],l[i][j-1]);
				if(l[i-1][j]==l[i][j]) f[i][j]+=f[i-1][j];
				if(l[i][j]==l[i][j-1]) f[i][j]+=f[i][j-1];
				if(l[i-1][j-1]==l[i][j])f[i][j]-=f[i-1][j-1];
				f[i][j]%=tim;
			}
			else{
				l[i][j]=l[i-1][j-1]+1;
				f[i][j]=f[i-1][j-1];
				if(l[i-1][j]==l[i][j])f[i][j]+=f[i-1][j];
				if(l[i][j-1]==l[i][j])f[i][j]+=f[i][j-1];
				f[i][j]%=tim;
			}
		}
	}
	printf("%d\n%d",l[lena][lenb],f[lena][lenb]);
}
int getmax(int x,int y){
	if(x>y)return x;
	return y;
}