【题目描述】
给定两个整数序列，写一个程序求它们的最长上升公共子序列。
当以下条件满足的时候，我们将长度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
【源程序】
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<string>#include<cstdlib>#include<queue>#include<vector>#define INF 0x3f3f3f3f#define PI acos(-1.0)#define N 501#define MOD 100001#define E 1e-12using namespace std;struct Node{int len;int ans[N];}order[N],now;int a[N],b[N];int main(){int n,m;cin>>n;for(int i=1;i<=n;++i)cin>>a[i];cin>>m;for(int i=1;i<=m;++i)cin>>b[i];for(int i=1;i<=m;++i){now.len=0;memset(now.ans,0,sizeof(now.ans));for(int j=1;j<=n;++j){if(a[j]<b[i]&&order[j].len>now.len)now=order[j];if(a[j]==b[i]){order[j]=now;order[j].len++;order[j].ans[order[j].len]=a[j];}}}int flag=0;int maxx=-INF;for(int i=1;i<=n;++i)if(order[i].len>maxx){maxx=order[i].len;flag=i;}cout<<order[flag].len<<endl;for(int i=1;i<=order[flag].len;++i)cout<<order[flag].ans[i]<<" ";cout<<endl;return 0;}
如果觉得《最长公共子上升序列（信息学奥赛一本通-T1306）》对你有帮助，请点赞、收藏，并留下你的观点哦！
