题解 CF10D 【LCIS】

xiaohuang · 2019-07-30 20:34:03 · 题解

更好的阅读体验

Solution

用\texttt{f[i][j]}表示\texttt{A}与\texttt{B}构成的以b_j为结尾的最长公共上升子序列的长度。

动态转移方程为：

而k这一维可以省去，在状态转移后记录最大符合要求的f[k]作为下一次的转移，正确性仍旧不变。

所以，最后的时间复杂度为O(n^2)。

Code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

const int MAXN = 505;
int n, m, a[MAXN], b[MAXN], ans[MAXN], dp[MAXN], scheme[MAXN];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
        scanf("%d", &b[i]);
    for (int i = 1; i <= n; i++) {//动态规划主要部分
        int id = 0;
        for (int j = 1; j <= m; j++) {
            if (a[i] == b[j]) {
                dp[j] = dp[id] + 1;
                scheme[j] = id;
            }
            if (a[i] > b[j] && dp[id] < dp[j]) id = j;
        }
    }
    int id = 0;
    for (int i = 1; i <= m; i++)
        if (dp[i] > dp[id]) id = i;
    printf("%d\n", dp[id]);
    int top = 0;
    while (dp[id]--) {
        ans[++top] = b[id];
        id = scheme[id];
    }
    for (int i = top; i >= 1; i--)
        printf("%d ", ans[i]);//输出方案前需要记录
    return 0;
}