【简单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
", ans );
    for(int i=0; i<ans; i++)
        printf("%d%c", lcis[i], i==ans-1?'
':' ');

    return 0;
}