首页 > 其他 > 详细

最长公共子上升序列

时间:2017-07-18 22:58:00      阅读:252      评论:0      收藏:0      [点我收藏+]

 

 

总时间限制: 
10000ms
 
内存限制: 
65536kB
描述
给定两个整数序列,写一个程序求它们的最长上升公共子序列。
当以下条件满足的时候,我们将长度为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
我们考虑用用vector来储存数据
#include<cstdio>
#include<algorithm>
#include<vector>
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() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    for(int i=1;i<=n;i++) {
        tmp.num=0;
        tmp.point.clear();
        for(int j=1;j<=n;j++) {
            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]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    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]);
    return 0;
}

 

最长公共子上升序列

原文:http://www.cnblogs.com/sssy/p/7203085.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!