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

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=5500;
int len1,len2;
int f[maxn][maxn],c[maxn][maxn];
string s,ss,s1,s2;
int _m(int,int);
int q(int);
void Init();
int main()
{
	freopen("lcs.in","r",stdin);
	freopen("lcs.out","w",stdout);
	cin>>s>>ss;
	len1=s.length(),len2=ss.length();
	s1=s.substr(0,len1-1);
	s2=ss.substr(0,len2-1);
	len1=s1.length();
	len2=s2.length();
	Init();
	return 0;
}
void Init()
{
	for(int i=1;i<=len1;i++)
	{
		for(int j=1;j<=len2;j++)
		{
			if(s1[i-1]==s2[j-1])
			{
				f[i][j]=f[i-1][j-1]+1;
			}
			else
			{
				f[i][j]=_m(f[i-1][j],f[i][j-1]);
			}
		}
	}
	printf("%d\n",f[len1][len2]);
	for(int i=0;i<=len1;i++)
	{
		c[i][0]=1;
	}
	for(int j=0;j<=len2;j++)
	{
		c[0][j]=1;
	}
	c[1][1]=1;
	for(int i=1;i<=len1;i++)
	{
		for(int j=1;j<=len2;j++)
		{
			if(s1[i-1]==s2[j-1])
			{
				c[i][j]=c[i-1][j-1];
				if(f[i][j]==f[i-1][j])
				{
					c[i][j]=c[i-1][j]+c[i][j];
				}
				if(f[i][j]==f[i][j-1])
				{
					c[i][j]=c[i][j-1]+c[i][j];
				}
			}
			else
			{
				if(f[i-1][j]==f[i][j]&&f[i][j-1]==f[i][j])
				{
					c[i][j]=c[i-1][j]+c[i][j-1];
					if(f[i][j]==f[i-1][j-1])
					{
						c[i][j]=c[i][j]-c[i-1][j-1];
					}
				}
				else
				{
					if(f[i-1][j]>f[i][j-1])
					{
						c[i][j]=c[i-1][j];
					}
					if(f[i-1][j]<f[i][j-1])
					{
						c[i][j]=c[i][j-1];
					}
				}
			}//
			c[i][j]=q(c[i][j]);
		}
	}
	printf("%d ",c[len1][len2]);
}
int _m(int a,int b)
{
	if(a<b)
	{
		return b;
	}
	return a;
}
int q(int a)
{
	return a%100000000;
}