题解【AcWing272】最长公共上升子序列

一道线性 DP 好题。

设 \(dp_{i,j}\) 表示在所有 \(a_{1\dots i}\)，\(b_{1\dots j}\) 的子序列中，以 \(b_j\) 结尾的最长公共上升子序列的最大长度。

转移的时候考虑 \(2\) 种情况：

若不选择 \(a_i\)，则 \(dp_{i,j}=dp_{i-1,j}\)；
若选择 \(a_i\)，则 \(dp_{i,j} = \max_{1\leq k \leq j，b_k < b_j}\{dp_{i-1,k}\}+1\)。又因为有 \(a_i=b_j\)，所以 \(dp_{i,j} = \max_{1\leq k \leq j，b_k < a_i}\{dp_{i-1,k}\}+1\)。

转移的代码：

for (int i = 1; i <= n; i+=1)

    for (int j = 1; j <= n; j+=1)

    {

        dp[i][j] = dp[i - 1][j];

        if (a[i] == b[j])

        {

            int maxdp = 0;

            for (int k = 1; k < j; k+=1)

                if (b[k] < a[i])

                    maxdp = max(maxdp, dp[i - 1][k]);

            dp[i][j] = max(dp[i][j], maxdp + 1);

        }

    }

这样转移的复杂度其实是 \(O(n^3)\) 的，明显会超时。

于是我们考虑优化，即对转移的代码进行等价变形。

我们发现，第三重循环能够转移的状态其实是所有小于 \(j\) 的 \(k\)，且 \(b_k < a_i\)。因为 \(a_i\) 的值是不变的，所以我们可以预处理出所有 \(dp_{i,k}(k<j)\) 的最大值，即 \(dp_{i,j}\) 的前缀最大值。

具体做法就是将变量 maxdp 移到第二层循环外，然后如果 \(b_j < a_i\) 就将 maxdp 与 \(dp_{i,j}\) 取 \(\max\)。

完整代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 3003;

int n, m;

int a[N], b[N], dp[N][N];

int main()

{

    cin >> n;

    for (int i = 1; i <= n; i+=1)

        cin >> a[i];

    for (int i = 1; i <= n; i+=1)

        cin >> b[i];

    for (int i = 1; i <= n; i+=1)

    {

        int maxdp = 0;

        for (int j = 1; j <= n; j+=1)

        {

            dp[i][j] = dp[i - 1][j];

            if (a[i] == b[j]) dp[i][j] = max(dp[i][j], maxdp + 1); //转移

            if (b[j] < a[i]) maxdp = max(maxdp, dp[i][j]); //前缀最大值

        }

    }

    int ans = 1;

    for (int i = 1; i <= n; i+=1) ans = max(ans, dp[n][i]);

    cout << ans << endl;

    return 0;

}

巴特西

题解【AcWing272】最长公共上升子序列

最新文章

热门文章