记录编号	241942	评测结果	AAAAA
题目名称	DNA螺旋串	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2016-03-26 11:09:12	内存使用	6.46 MiB

#include<cstdio>
#include<cstring> 
using namespace std;
const int maxn = 1000 + 10 ;
inline int cat_max(const int a,const int b){
	return a>b? a:b;
}
char s1[maxn],s2[maxn];
int f[maxn][maxn];
int flag[maxn][maxn];
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) - 1;
	int len2 = strlen(s2) - 1;
	for(int i=1;i<=len1;i++)
		for(int j=1;j<=len2;j++){
			if( s1[i] == s2[j] ){
				f[i][j] = f[i-1][j-1] + 1 ;
				flag[i][j]=0;
			}
			else if(f[i-1][j]>=f[i][j-1]){
				f[i][j]=f[i-1][j];
				flag[i][j]=1;
			}
			else f[i][j]=f[i][j-1],flag[i][j]=2;
		}
	printf("%d\n",f[len1][len2]);	
	int up_side = f[len1][len2];
	char ans[5010];
	int i = len1,j=len2;
	while(f[i][j]!=0){
		if(flag[i][j]==0){ans[--up_side]=s1[i];i--;j--;}
		else if(flag[i][j]==1) i--;
		else if(flag[i][j]==2) j--;
	}
	printf("%s",ans);
	return 0;
}