记录编号	418431	评测结果	AAAAAAAAAA
题目名称	最长公共子序列	最终得分	100
用户昵称	sakura	是否通过	通过
代码语言	C++	运行时间	0.483 s
提交时间	2017-06-30 11:26:28	内存使用	96.07 MiB

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
string s1,s2;
const int maxn=5010;
char a[maxn],b[maxn];int f[maxn][maxn],len1,len2;
inline void dp(){
	for (int i=0;i<len1;i++){
		for (int j=0;j<len2;j++){
			if(a[i]==b[j]){
				f[i+1][j+1]=f[i][j]+1;
			}
			else{
				f[i+1][j+1]=max(f[i][j+1],f[i+1][j]);
			}
		}
	}
}
int main()
{
	freopen("lcslength.in","r",stdin);
	freopen("lcslength.out","w",stdout);
	cin>>s1>>s2;
	len1=s1.size();
	len2=s2.size();
	
	int i=0;
	while(s1[i]!='.')
	{
		a[i]=s1[i];
		i++;
	}
	len1=i;
	i=0;
	while(s2[i]!='.')
	{
		b[i]=s2[i];
		i++;
	}
	len2=i;
//	for(int i=1;i<=s1.size();i++)
//	a[i]=s1[i];
//	for(int j=1;j<=s2.size();j++)
//	b[j]=s2[j];
	
	dp();
	
	int ans=0;
	for(int i=0;i<=len1;i++)
	for(int j=0;j<=len2;j++)
	ans=max(f[i][j],ans);
	
	cout<<ans;
}