记录编号	31750	评测结果	AAAAAAAAAA
题目名称	最长公共子序列	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	1.114 s
提交时间	2011-11-03 17:52:55	内存使用	48.06 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
char A[5005];
char B[5005];
int la;
int lb;
unsigned short int PP[5005][5005];

int Max(int a,int b,int c)
{
	if(b>a)
		a=b;
	if(c>a)
		a=c;
	return a;
}

bool same(int i,int j)
{
	if(A[i]==B[j])
		return 1;
	else
		return 0;
}

void init()
{
	cin>>A>>B;
	la=strlen(A);
	lb=strlen(B);
}


void dp()
{
	
	int MAXN=0;
	
	for (int i=0;i<la;i++)
	{
		for (int j=0;j<lb;j++)
		{
			PP[i+1][j+1]=Max(PP[i][j]+same(i,j),PP[i][j+1],PP[i+1][j]);
			if(PP[i+1][j+1]>MAXN)
				MAXN=PP[i+1][j+1];
		}
	}
	cout<<MAXN-1<<endl;
}

int main()
{
	freopen("lcslength.in","r",stdin);
	freopen("lcslength.out","w",stdout);
	init();
	dp();
	return 0;
}