ACwing 272 LCIS 最长公共上升子序列
题面
对于两个数列 A 和 B,如果它们都包含一段位置不一定连续的数,且数值是严格递增的,那么称这一段数是两个数列的公共上升子序列
给定序列 \(A\) 和 \(B\) ,求 \(A\) 和 \(B\) 的最长公共上升子序列
\(|A,B| \le 3000\)
题解
设 \(f(i,j)\) 表示 \(A_1...A_i\) 和 \(B_1...B_j\) 以 \(B_j\) 为结尾的 LCIS ,可以分两种情况转移
- \(A_i \not= B_j\) ,\(f(i,j) = f(i - 1, j)\)
- \(A_i = B_j\) ,\(f(i,j) = \max_{k < j,B_k < B_j} \{f(i - 1, k)\} + 1\)
转移的候选状态集合是只增不减的,所以可以用一个变量维护,转移时间复杂度降为 \(O(1)\) 总时间复杂度为 \(O(n^2)\)
code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;const int N = 3e3 + 10;int n;
int a[N], b[N];
int f[N][N];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 val = 0;for (int j = 1; j <= n; j++) {if (a[i] == b[j]) {f[i][j] = val + 1;} else {f[i][j] = f[i - 1][j];}if (b[j] < a[i]) val = max (val, f[i - 1][j]);}}int ans = 0;for (int i = 1; i <= n; i++) {ans = max (ans, f[n][i]);}cout << ans << endl;return 0;
}