题解：P10954 LCIS【数据暂时有误】

· · 题解

题意：

给出两个数组a,b. 求最长上升公共子序列.

解答

首先想到dp.

定义状态

表示第一个数组中前i个数和第二个数组中前j个数而且结尾为第二个数组中第j个数结尾的LCIS.

转移方程

当a_i=b_j时， 可以选择任意一个比b_j小的数做LCIS中上一个数， 因为如果不选这个公共数时， 上一对公共数在选择这个数时也可以选到， 且区间更小， 故选这一对数更优.

当a_i!=b_j时， 用a_{i-1},b_j的dp值，即寻找公共数对.

即dp_{i,j}=max(dp_{i-1,k})(k<j) + 1(a_i=b_j),

dp_{i,j}=dp_{i-1,j}(a_i!=b_j).

code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, a[N], b[N], dp[N][N], ans;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (a[i] == b[j]) 
                for (int k = 1; k < j; k++){
                    if (b[k] < b[j]) 
                        dp[i][j] = max(dp[i][j], dp[i - 1][k] + 1);
                }
            else dp[i][j] = dp[i - 1][j];
            ans = max(ans, dp[i][j]);
        }
    cout << ans << endl;
    return 0;
}

时间复杂度O(n^3) 很明显过不了, 需要优化！

for (int k = 1; k < j; k++){
    if (b[k] < b[j]) 
        dp[i][j] = max(dp[i][j], dp[i - 1][k] + 1);
}

这一部分时间复杂度较高, 可以优化.

最终code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, a[N], b[N], dp[N][N], ans;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) {
        int maxv = dp[i - 1][0];
        for (int j = 1; j <= n; j++) {
            if (a[i] == b[j]) dp[i][j] = maxv + 1;
            else dp[i][j] = dp[i - 1][j];
            if (b[j] < a[i]) maxv = max(maxv, dp[i - 1][j]);
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << endl;
    return 0;
}