题目描述
ACWing 题目链接
NOI onlinejudge 题目链接
Codeforces 10D LCIS
给定一个长度为 (n) 的序列 (a)，一个长度为 (m) 的序列 (b)，求他们的最长的公共上升子序列的长度。
题目分析
考虑状态设置为最长公共子序列和最长上升子序列的状态"合并"在一起的状态。
设 (f[i][j]) 为 (a) 前 (i) 个和 (b) 前 (j) 个匹配的最长公共上升子序列以 (b[j]) 结尾的长度。（其实这里设置成 (a[i]) 结尾也可以，只不过为了后面好转移设的是 (b[j])）
转移方程就很好推了:
感性理解一下：
如果 (a[i] eq b[j]) ，则这里转移一定要从 (f[k][j] (1leq k<j)) 的最大值转移而来，因为结尾必须是 (b[j])，所以第二维一定是 (j)，第一维的 (k) 显然取 (i-1) 最优，因为前 ((i-1)) 的 (a) 一定不如前 (i) 的 (a) 匹配的结果更优。
如果 (a[i]==b[j])，则从前面选一个 (f[l][k]) 来转移，同上这里 (l) 取 (i-1) 最优，也就是对于一个 (f[i-1][k])，如果 (b[k]<b[j])，则这个 (b[j]) 是可以从这个 (b[k]) 接上来的，但是 (k) 在 (j) 前面有很多取值，所以要全部遍历一遍取值。
注: 以下复杂度默认 (n,m) 同阶。
这样的暴力转移是 (mathcal{O}(n^3)) 的，考虑优化:
首先因为 (a[i]==b[j])，所以里面那个 (max) 可以写成这个形式
这样就好办了，先枚举 (i) 在枚举 (j) ，在枚举 (j) 的过程中动态更新每一个 (max) 的值，就可以做到 (mathcal{O}(n^2)) 更新。
具体地：如果枚举到的 (b[j]<a[i])，则为后面的 (j) 更新 (max{f[i-1][k] (1leq k<j&&b[k]<a[i])})，转移的时候直接使用即可。
值得注意的是，转移方程只用到了 (f[i]) 和 (f[i-1])，显然 (i) 这一维可以滚动数组，空间复杂度优化到 (mathcal{O}(n))。
(mathcal{Code})
ACWing
#include<iostream>
#include<cstdio>
inline int Max(int x, int y) { return x > y ? x : y; }
inline int read() {
int r = 0; bool w = 0; char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-') w = 1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
r = (r << 3) + (r << 1) + (ch ^ 48);
ch = getchar();
}
return w ? ~r + 1 : r;
}
const int N = 3010;
int n, m, ans;
int a[N], b[N], f[2][N];
signed main() {
n = m = read();
for(int i = 1; i <= n; ++i)
a[i] = read();
for(int i = 1; i <= m; ++i)
b[i] = read();
for(int i = 1; i <= n; ++i) {
int maxx = 0;
for(int j = 1; j <= m; ++j) {
if(a[i] == b[j]) f[i&1][j] = maxx + 1;
else f[i&1][j] = f[!(i&1)][j];
if(a[i] > b[j]) maxx = Max(maxx, f[!(i&1)][j]);
}
}
for(int i = 1; i <= m; ++i)
ans = Max(ans, f[n&1][i]);
printf("%d
", ans);
return 0;
}
后两道题还需要再记录路径，这部分的思考留给读者。