输入

第1行：字符串A
第2行：字符串B
(A,B的长度 <= 1000)

输出

输出最长的子序列，如果有多个，随意输出1个。

输入样例

abcicba
abdkscab

输出样例

abca

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 char a[1020],b[1020];
 7 int f[1020][1020];
 8 int ans[1020][1020];
 9 void dfs(int x,int y){
10     if(x==0||y==0) return;
11     if(ans[x][y]==0){
12         dfs(x-1,y-1);
13         cout<<b[y];
14     }
15     else if(ans[x][y]==1){
16         dfs(x-1,y);
17     }
18     else{
19         dfs(x,y-1);
20     }
21 }
22 int main(){
23     cin>>a>>b;
24     int l1=strlen(a),l2=strlen(b);
25     for(int i=l1;i>=1;i--) a[i]=a[i-1];
26     for(int i=l2;i>=1;i--) b[i]=b[i-1];
27     for(int i=1;i<=l1;i++){
28         for(int j=1;j<=l2;j++){
29             if(a[i]==b[j]){
30                 f[i][j]=f[i-1][j-1]+1;
31                 ans[i][j]=0;
32             }
33             else if(f[i-1][j]>=f[i][j-1]){
34                 f[i][j]=f[i-1][j];
35                 ans[i][j]=1;
36             }
37             else{
38                 f[i][j]=f[i][j-1];
39                 ans[i][j]=-1;
40             }
41         }
42     }
43     //cout<<f[l1][l2];
44     dfs(l1,l2);
45     return 0;
46 }