记录编号	259088	评测结果	AAAAA
题目名称	DNA螺旋串	最终得分	100
用户昵称	竹语淡墨	是否通过	通过
代码语言	C++	运行时间	0.158 s
提交时间	2016-05-08 07:25:34	内存使用	24.69 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>

using namespace std;

void Work();
void Getpath(int,int);

char a[2001];
char b[2001];
int f[2001][2001];
int flag[2001][2001];
int la,lb;

int main()
{
	freopen("lcsdna.in","r",stdin);
	freopen("lcsdna.out","w",stdout);
	
	memset(flag,0,sizeof(flag));
	
	Work();
	Getpath(la,lb);

	return 0;
}

void Work()
{
	scanf("%s%s",a+1,b+1);
	
	la=strlen(a+1);	
	lb=strlen(b+1);
	
	for(int i=1;i<=la;i++)
	{
		for(int j=1;j<=lb;j++)
		{
			if(a[i]==b[j])
			{
				f[i][j]=max(max(f[i-1][j],f[i][j-1]),f[i-1][j-1]+1);
				flag[i][j]=1;
			}
			else
			{
				f[i][j]=max(f[i-1][j],f[i][j-1]);
				if(f[i][j]==f[i-1][j])
				{
					flag[i][j]=2;
				}
				else
				{
					flag[i][j]=3;
				}
			}
		}
	}
	
	printf("%d\n",f[la][lb]);
}

void Getpath(int i,int j)
{
	if(i==0||j==0)
	{
		return;
	}
	
	if(flag[i][j]==1)
	{
		Getpath(i-1,j-1);
		printf("%c",a[i]);
	}
	else if(flag[i][j]==2)
	{
		Getpath(i-1,j);
	}
	else
	{
		Getpath(i,j-1);
	}
}