【题目描述】
给出两个序列，求出最长公共上升子序列的长度，并输出其中一个解。
【题目链接】
http://noi.openjudge.cn/ch0206/2000/
【算法】
经典问题，结合了LIS和LCS。
【代码】
1 #include <bits/stdc++.h> 2 using namespace std; 3 int len1,len2,i,j,ans,ri,rj; 4 int s1[510],s2[510],rec[510][510],dp[510][510]; 5 void print(int x,int y) 6 { 7 switch(rec[x][y]) { 8 case -1: print(x-1,y); break; 9 case 0: printf("%d",s2[y]); break; 10 default: print(x-1,rec[x][y]),printf(" %d",s2[y]); 11 } 12 } 13 int main() 14 { 15 scanf("%d",&len1); 16 for(i=1;i<=len1;i++) scanf("%d",&s1[i]); 17 scanf("%d",&len2); 18 for(i=1;i<=len2;i++) scanf("%d",&s2[i]); 19 for(i=1;i<=len1;i++) { 20 int val=0,tmp=0; 21 for(j=1;j<=len2;j++) { 22 if(s1[i]==s2[j]) dp[i][j]=val+1,rec[i][j]=tmp; 23 else dp[i][j]=dp[i-1][j],rec[i][j]=-1; 24 if(s1[i]>s2[j]&&dp[i-1][j]>val) val=dp[i-1][j],tmp=j; 25 if(dp[i][j]>ans) ans=dp[i][j],ri=i,rj=j; 26 } 27 } 28 printf("%d ",ans); 29 print(ri,rj); 30 return 0; 31 }