【简单dp】poj 2127 Greatest Common Increasing Subsequence【最长公共上升子序列】【模板】

Sample Input

5

1 4 2 5 -12

4

-12 1 2 4

Sample Output

2

1 4

题目：给你两个数字序列，求出这两个序列的最长公共上升子序列。
输出最长的长度，并打表输出。可能存在多种正确答案，故此题是special judge！

分析：dp[i][j] : A[1...i]和B[1...j]的公共上升子序列中以B[j]为结尾的最长的长度。
如果A[i] != B[j], 则dp[i][j]=d[i-1][j]; 也就是说当前这个A[i]是没效用的。
如果A[i] = B[j], 则dp[i][j]=max( dp[i][k]+1 ),其中 k<j 且 A[i]>B[k]
时间复杂度O(n^2)

注意：
n1 n2位两个序列的长度， 
A[] B[]为两个序列数组，
ans 全局变量 最长公共子序列的长度值
lcis 最长公共上升子序列 打表存储

代码：

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <ctype.h>

#include <math.h>

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

int n1, n2;

int A[510], B[510];

int dp[510][510];

int pre[510][510];

int lcis[510];

int ans;

void get_LCIS()

{

    memset(dp, 0, sizeof(dp));

    memset(pre, 0, sizeof(pre));

    int i, j;

    for(i=1; i<=n1; i++){

        int k=0;

        for(j=1; j<=n2; j++){

            if(A[i] != B[j]) dp[i][j]=dp[i-1][j];

            if(A[i]>B[j] && dp[i][j]>dp[i][k]) k=j;

            if(A[i]==B[j]){

                dp[i][j]=dp[i][k]+1;

                pre[i][j]=k;

            }

        }

    }

    ans=-1;

    int x=n1, y=0;

    for(i=1; i<=n2; i++){

        if(dp[n1][i]>ans){

            ans=dp[n1][i]; y=i;

        }

    }

    int cnt=1;

    while(dp[x][y]){

        if(A[x] != B[y]) x--;

        else{

            lcis[ans-cnt]=B[y];

            cnt++;

            y=pre[x][y];

        }

    }

}

int main()

{

    scanf("%d", &n1);

    for(int i=1; i<=n1; i++) scanf("%d", &A[i]);

    scanf("%d", &n2);

    for(int i=1; i<=n2; i++) scanf("%d", &B[i]);

    get_LCIS();

    printf("%d\n", ans );

    for(int i=0; i<ans; i++)

        printf("%d%c", lcis[i], i==ans-1?'\n':' ');

    return 0;

}

巴特西

【简单dp】poj 2127 Greatest Common Increasing Subsequence【最长公共上升子序列】【模板】

最新文章

热门文章