给一个序列a和序列b，求他们的最长公共上升子序列
///LCIS 最长公共上升子序列 #include<cstdio> #include<algorithm> using namespace std; int a[555],b[555],dp[555];//dp[i]表示以b[j]结尾的序列的LCIS长度为多少 int path[555],pre[555],ans=0; int main(){ int x,y; scanf("%d",&x); for(int i=1;i<=x;i++) scanf("%d",&a[i]); scanf("%d",&y); for(int j=1;j<=y;j++) scanf("%d",&b[j]); for(int i=1; i<=x;i++){ int pos=0;//pos记录上一个位置，用于后来输出路径 for(int j=1; j<=y;j++){ if(a[i]==b[j]) dp[j]=dp[pos]+1,pre[j]=pos;///如果a[i]==b[i]，那么就发生转移，记录上一个位置 if(b[j]<a[i]&&dp[pos]<dp[j]) pos = j; //目前循环到b[j]<要进行比较的a[i]，而且以j为结尾的LCIS大于以pos结尾的，那么我们更新pos，去找一个更大b[j]等于a[i] } } int pos=0; for(int i=1;i<=y;i++){ if(ans<dp[i]){ ans=dp[i]; pos=i; } } for(int i=1;i<=ans;i++){ path[i]=b[pos]; pos=pre[pos]; } printf("%d\n",ans); for(int i=ans;i>=1;i--){ if(i!=1) printf("%d ",path[i]); else printf("%d\n",path[i]); } return 0; }