记录编号	23270	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]最长公共子序列	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	1.863 s
提交时间	2011-03-06 14:03:42	内存使用	0.32 MiB

#include <iostream>
#include <fstream>
#include <string>
#include <cstring>

using namespace std;

string s1, s2;
short f[2][5001];
int g[2][5001];

int main ()
{
	ifstream fin("lcs.in");
	ofstream fout("lcs.out");

	fin >> s1 >> s2;
	s1.erase(s1.end()-1);
	s2.erase(s2.end()-1);

	for (int i=0; i<s2.length(); i++)
		g[1][i] = 1;
	
	for (int i=0; i<s1.length(); i++)
	{
		if (s1[i] == s2[0])
		{
			f[i%2][0] = 1;
			g[i%2][0] = 1;
			if (f[(i+1)%2][0] == f[i%2][0])
				g[i%2][0] += g[(i+1)%2][0];
		}
		else
			f[i%2][0] = f[(i+1)%2][0],
			g[i%2][0] = g[(i+1)%2][0];

		for (int j=1; j<s2.length(); j++)
		{
			if (s1[i] == s2[j])
			{
				g[i%2][j] = g[(i+1)%2][j-1];
				f[i%2][j] = f[(i+1)%2][j-1] + 1;

				if (f[(i+1)%2][j] == f[i%2][j])
					g[i%2][j] += g[(i+1)%2][j];

				if (f[i%2][j-1] == f[i%2][j])
					g[i%2][j] += g[i%2][j-1];
			}
			else
			{
				if (f[(i+1)%2][j] > f[i%2][j-1])
					f[i%2][j] = f[(i+1)%2][j],
					g[i%2][j] = g[(i+1)%2][j];
				else if (f[(i+1)%2][j] == f[i%2][j-1])
				{
					f[i%2][j] = f[(i+1)%2][j];
					g[i%2][j] = g[(i+1)%2][j] + g[i%2][j-1];

					if (f[i%2][j] == f[(i+1)%2][j-1])
						g[i%2][j] -= g[(i+1)%2][j-1];
				}
				else
					f[i%2][j] = f[i%2][j-1],
					g[i%2][j] = g[i%2][j-1];
			}
			
			g[i%2][j] %= 100000000;
		}
	}

	fout << f[(s1.length()-1)%2][s2.length()-1] << endl;
	fout << g[(s1.length()-1)%2][s2.length()-1] << endl;

	return 0;
}