记录编号	241792	评测结果	WAAAA
题目名称	DNA螺旋串	最终得分	80
用户昵称	liu_runda	是否通过	未通过
代码语言	C++	运行时间	0.003 s
提交时间	2016-03-26 09:01:20	内存使用	2.48 MiB

#include<cstdio>
#include<cstring>
const int maxn=505;
char s1[maxn],s2[maxn];
int f[maxn][maxn];
int p[maxn][maxn];//0:end 1:up 2:left 3:leftup
char last[maxn][maxn];
int max(int a,int b){
	return a>b?a:b;
}
void output(int i,int j){
	if(p[i][j]==0)return;
	else{
		if(p[i][j]==3){
			output(i-1,j-1);
			printf("%c",last[i][j]);
		}else if(p[i][j]==2){
			output(i,j-1);
		}else output(i-1,j);
	}
}
int main(){
	freopen("lcsdna.in","r",stdin);
	freopen("lcsdna.out","w",stdout);
	scanf("%s %s",s1+1,s2+1);
	s1[0]=s2[0]='.';
	int len1=strlen(s1),len2=strlen(s2);
	for(int i=1;i<len1;++i){
		for(int j=1;j<len2;++j){
			if(f[i][j-1]>=f[i-1][j]){
				f[i][j]=f[i][j-1];
				last[i][j]=last[i][j-1];
				p[i][j]=2;
			}else{
				f[i][j]=f[i-1][j];
				last[i][j]=last[i-1][j];
				p[i][j]=1;
			}
			if(s1[i]==s2[j]){
				if(f[i-1][j-1]+1>f[i][j]){
				
					f[i][j]=f[i-1][j-1]+1;
					last[i][j]=s1[i];
					p[i][j]=3;
					
				}
			}
		}
	}
	printf("%d\n",f[len1-1][len2-1]);
	output(len1-1,len2-1);
	fclose(stdin);fclose(stdout);
	return 0;
}