信息学奥赛一本通T1306：最长公共子上升序列

【题目描述】

给定两个整数序列，写一个程序求它们的最长上升公共子序列。

当以下条件满足的时候，我们将长度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-12
using 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：动态规划经典问题 最长公共子上升序列 归属于 动态规划经典问题，更多同类题解源程序见：动态规划经典问题 和 最长公共子上升序列