一道线性 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;
}