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

#include<cstdio>
#include<cstring>
#define max(a,b) a>b?a:b
using namespace std;
const int maxn=5010;
const int Inf=100000000;
int f[2][maxn],cnt[2][maxn];
int MY(){
	freopen("lcs.in","r",stdin);
	freopen("lcs.out","w",stdout);
	char s1[maxn],s2[maxn];
	scanf("%s%s",s1+1,s2+1);	
	int m=strlen(s1+1)-1,n=strlen(s2+1)-1;
	bool t=0;
	for(int i=0;i<=n;i++)cnt[0][i]=1;
	for(int i=1;i<=m;i++){
		t=!t;
		memset(cnt[t],0,sizeof(cnt[t]));
		cnt[t][0]=1;
		for(int j=1;j<=n;j++){
			if(s1[i]==s2[j]){
				f[t][j]=f[!t][j-1]+1;
				cnt[t][j]=cnt[!t][j-1];
				if(f[t][j]==f[!t][j])cnt[t][j]+=cnt[!t][j];
				if(f[t][j]==f[t][j-1])cnt[t][j]+=cnt[t][j-1];
				cnt[t][j]%=Inf;
			}
			else{
				f[t][j]=max(f[t][j-1],f[!t][j]);
				if(f[t][j]==f[!t][j])cnt[t][j]+=cnt[!t][j];
				if(f[t][j]==f[t][j-1])cnt[t][j]+=cnt[t][j-1];
				if(f[t][j]==f[!t][j-1])cnt[t][j]-=cnt[!t][j-1];
				cnt[t][j]%=Inf;
			}
		}		
	}
	printf("%d\n%d\n",f[t][n],cnt[t][n]);
	
}
int YOU=MY();
int main(){;}