stonechina0616

描述给定两个整数序列，写一个程序求它们的最长上升公共子序列。
当以下条件满足的时候，我们将长度为N的序列S1 , S2 , . . . , SN 称为长度为M的序列A1 , A2 , . . . , AM的上升子序列：

存在 1 <= i1 < i2 < . . . < iN <= M ，使得对所有 1 <= j <=N，均有Sj = Aij，且对于所有的1 <= j < N，均有Sj < Sj+1。

输入每个序列用两行表示，第一行是长度M(1 <= M <= 500)，第二行是该序列的M个整数Ai (-231 <= Ai < 231 )
输出在第一行，输出两个序列的最长上升公共子序列的长度L。在第二行，输出该子序列。如果有不止一个符合条件的子序列，则输出任何一个即可。
样例输入5 1 4 2 5 -12 4 -12 1 2 4样例输出2 1 4

计算长度可以按照最长公共子序列O(n^2)的做法修改，只需要将状态转移时的a[i]!=b[j]改为a[i]>b[j]。但是这道题的难点是记录这个子序列。这里可以用到vector数组，当a[i]=b[j]时，dp[i]=max(dp[k])+1,dp[i].push_back(a[i])由于Openjudge没有Special judge，枚举时需要注意一下。
代码：#include<cstdio>#include<algorithm>#include<cstring>#include<iostream>#include<vector>#define rep(q,p) for(int q=1;q<=p;q++)using namespace std;const int maxn=505;int n,m,a[maxn],b[maxn];struct hehe{ int num; vector<int>point;}dp[maxn],tmp,ans;
int main(){ freopen("in.txt","r",stdin); scanf("%d",&n); rep(i,n) scanf("%d",&a[i]); scanf("%d",&m); rep(i,m) scanf("%d",&b[i]); rep(i,m) { tmp.num=0; tmp.point.clear(); rep(j,n) { if (b[i]>a[j] && dp[j].num>tmp.num) tmp=dp[j]; if (a[j]==b[i]) { dp[j]=tmp; dp[j].num=tmp.num+1; dp[j].point.push_back(a[j]); } } } rep(i,n) if (dp[i].num>ans.num) ans=dp[i]; printf("%d\n",ans.num); for (int k=0;k<ans.point.size();k++) printf("%d ",ans.point[k]); printf("\n"); return 0;}