记录编号	388347	评测结果	WWWWWWWWWWWWWWW
题目名称	[HZOI 2016] 最长公共上升子序列	最终得分	0
用户昵称	Hyoi_ctime	是否通过	未通过
代码语言	C++	运行时间	0.003 s
提交时间	2017-03-28 20:39:10	内存使用	95.72 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int max(int a,int b){
	return a>b? a:b;
}
const int maxlen=5001;
int c[maxlen][maxlen];
string z="";
int main()
{
	freopen("lcis.in","r",stdin);
	freopen("lcis.out","w",stdout);
	int n,j,l1,l2,a,b;
	char x[maxlen],y[maxlen];
	
	scanf("%d%d",&x,&y);
	l1=strlen(x);l2=strlen(y);
	for(int i=1;i<=l1;i++)
	 for(int j=1;j<=l1;j++)
	  if(x[i-1]==y[i-1])
	    c[i][j]=c[i-1][j-1]+1;
	    else
	      c[i][j]=max(c[i-1][j],c[i][j-1]);
//	printf("%d\n",c[l1][l2]+2);
	a=l1;
	b=l2;
	while(a&&b)
	 if(x[a-1]==y[b-1]){
	 	z=x[--a]+z;
	 	b--;
	 }
	 else{
	      if(c[a-1][b]>c[a][b-1])a--;
	      else b--;
	  }
	  printf("%s\n",z.c_str());
	  return 0;
	 
}