POJ 2127 -- Greatest Common Increasing Subsequence

题目链接：http://poj.org/problem?id=2127

Greatest Common Increasing Subsequence

Time Limit: 10000MS		Memory Limit: 65536K
Total Submissions: 12418		Accepted: 3229
Case Time Limit: 2000MS		Special Judge

Description

You are given two sequences of integer numbers. Write a program to determine their common increasing subsequence of maximal possible length. 
Sequence S₁ , S₂ , . . . , S_N of length N is called an increasing subsequence of a sequence A₁ , A₂ , . . . , A_M of length M if there exist 1 <= i₁ < i₂ < . . . < i_N <= M such that S_j = A_ij for all 1 <= j <= N , and S_j < S_j+1 for all 1 <= j < N .

Input

Each sequence is described with M --- its length (1 <= M <= 500) and M integer numbers A_i (-2³¹ <= A_i < 2³¹ ) --- the sequence itself.

Output

On the first line of the output file print L --- the length of the greatest common increasing subsequence of both sequences. On the second line print the subsequence itself. If there are several possible answers, output any of them.

Sample Input

5
1 4 2 5 -12
4
-12 1 2 4

Sample Outpu2题意：给出两个序列，求最长公共上升子序列的长度，并输出此子序列。题解&总结：1. 最长公共上升子序列问题(LCIS)+dp路径记录，下面第一份代码为LCIS模板代码和注释理解；

2. 由于LCIS可以重复利用一维dp数组而无需开二维dp数组，自然而然地会让人想到存路径能否也用一维，
   其实是不行的，用文字解释就是“在一个以满足上升的序列中，会有后面的替换之前的前驱”。比如：
   5
   2 3 4 1 2
   4
   1 2 3 4
   这组数据中，对照下面第二份代码来看，当i循环到4的时候，dp[1],dp[2],dp[3],dp[4]的前驱(即dp[j].pre)分别为0,0,2,3,
   此时还是正确的，但i为5的时候，dp[2].pre会被更新为1(此时的更新只是局部最优解的更新，但会影响到我们全局最优解的路径)，
   而1显然并不在正确路径中，因此一维存路径是不正确的，有必要用二维数组显示每次更新的前驱对应的i,j分别为多少，才能在后续还原路径时得出正确答案。

LCIS模板：

/*
  定义状态dp[i][j]表示a[1]~a[i], b[1]~b[j]中, 以b[j]结尾的最长公共上升子序列
  流程：
  1.a[i] != b[j], a[i]不能和b[j]匹配,a[i]对答案无贡献,那么 dp[i][j] = dp[i-1][j];
  2.a[i] == b[j], dp[i][j] = max(dp[i-1][1~(j-1)]) + 1;
    在循环的过程中维护maxx = max(dp[i-1][1~(j-1)]);
  对if (a[i] > b[j] && dp[i-1][j] > maxx)的解释：
  由于maxx是在a[i] == b[j]的情况下使用的,且在内层循环中a[i]不变,
  故a[i] > b[j]中维护的一系列maxx即为dp[i-1][1~(j-1)]且当a[i] == b[j]时能有a[i] > maxx所对应的a[i-1]和b[j];
*/
/*
#include <iostream>
#include <cstring>
#define MAXN 1010
#define REP(i, n) for (int i = 1; i <= n; i++)
using namespace std;
int a[MAXN], b[MAXN], dp[MAXN][MAXN], n, maxx, ans;

int main() {
    while (cin >> n) {
        ans = 0;
        memset(dp, 0, sizeof(dp));
        REP(i, n) cin >> a[i]; REP(i, n) cin >> b[i];
        REP(i, n) {
            maxx = 0;
            REP(j, n) {
                dp[i][j] = dp[i-1][j];
                if (a[i] > b[j] && dp[i-1][j] > maxx) maxx = dp[i-1][j];
                if (a[i] == b[j]) dp[i][j] = maxx + 1;
            }
        }
        REP(i, n) ans = max(ans, dp[n][i]);
        cout << ans << endl;
    }
    return 0;
} */

// 一维打法，dp的滚动使用，如01背包
#include <iostream>
#include <cstring>
#define MAXN 1010
#define REP(i, n) for (int i = 1; i <= n; i++)
using namespace std;
int a[MAXN], b[MAXN], dp[MAXN], n, maxx, ans;

int main() {
    while (cin >> n) {
        ans = 0;
        memset(dp, 0, sizeof(dp));
        REP(i, n) cin >> a[i]; REP(i, n) cin >> b[i];
        REP(i, n) {
            maxx = 0;
            REP(j, n) {
                if (a[i] > b[j] && dp[j] > maxx) maxx = dp[j];
                if (a[i] == b[j]) dp[j] = maxx + 1;
            }
        }
        REP(i, n) ans = max(ans, dp[i]);
        cout << ans << endl;
    }
    return 0;
}

 一维存路径WA代码：

#include <iostream>
#include <cstring>
#include <stack>
#define MAXN 510
#define REP(i, n) for (int i = 1; i <= n; i++)
using namespace std;
int a[MAXN], b[MAXN];
struct DP{
    int num, pre;
} dp[MAXN];

int main() {
    int n, m;
    while (cin >> n) {
        int ans = 0, pos;
        memset(dp, 0, sizeof(dp));
        REP(i, n) cin >> a[i];
        cin >> m; REP(i, m) cin >> b[i];
        REP(i, n) {
            int maxx = 0; pos = 0;
            REP(j, m) {
                if (a[i] > b[j] && dp[j].num > maxx) maxx = dp[j].num, pos = j;
                if (a[i] == b[j]) dp[j].num = maxx + 1, dp[j].pre = pos;
            }
        }
        REP(i, m) if (dp[i].num > ans) ans = dp[i].num, pos = i;
        stack<int> sta;
        while (pos) {
            sta.push(pos);
            pos = dp[pos].pre;
        }
        cout << ans << endl;
        while (!sta.empty()) {
            cout << b[sta.top()] << ' ';
            sta.pop();
        }
        cout << endl;
    }
    return 0;
}

 AC代码：

#include <iostream>
#include <cstring>
#include <stack>
#define MAXN 1010
#define REP(i, n) for (int i = 1; i <= n; i++)
using namespace std;
int a[MAXN], b[MAXN];
int dp[MAXN], pre[MAXN][MAXN];

int main() {
    int n, m;
    while (cin >> n) {
        REP(i, n) cin >> a[i];
        cin >> m;
        REP(i, m) cin >> b[i];
        memset(pre, -1, sizeof(pre));
        memset(dp, 0, sizeof(dp));
        REP(i, n) {
            int maxx = 0, posj = 0;
            REP(j, m) {
                if (a[i] > b[j] && dp[j] > maxx) maxx = dp[j], posj = j;
                if (a[i] == b[j]) dp[j] = maxx + 1, pre[i][j] = posj;
            }
        }
        int k = 1;
        REP(i, m) if (dp[i] > dp[k]) k = i;
        cout << dp[k] << endl;
        if (!dp[k]) continue;
        stack<int> ans;
        for (int i = n; i; i--) if (pre[i][k] != -1) ans.push(a[i]), k = pre[i][k];
        cout << ans.top(); ans.pop();
        while (!ans.empty()) cout << ' ' << ans.top(), ans.pop();
        cout << endl;
    }
    return 0;
}