CF10D LCIS - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
是远古的 CF 题一枚呀。
不难想到状态，\(f(i, j)\) 表示 \(A[1, i]\) 和 \(B[1, j]\) 内可构成的 LCIS 长度。
然后会发现，保证上升的这一部分转移是比较难以进行的，因为我们想得到单调性，却没有一个明确的比较目标。
回顾 LIS 的做法，\(f(i)\) 表示 \(A[1, i]\) 且以 \(A[i]\) 结尾的 LIS 长度。
那么修改状态，\(f(i, j)\) 表示 \(A[1, i]\) 和 \(B[1, j]\) 内，且以 \(B[j]\) 结尾的 LCIS 长度。
这样转移方程就很好写了，我们令 \(A[0] = B[0] = -\infty\)：
\[f(i, j) = \begin{cases} f(i - 1, j) & A[i] \ne B[j] \\ \max\limits_{0\le k < j, B[k] < B[j]}\{f(i - 1, k)\} + 1 & A[i] = B[j] \end{cases} \]边界：\(f(i, 0) = f(0, j) = 0\)。
容易看出，直接这么写是 \(\mathcal{O}(nm^2)\) 的。可能已经足以通过本题？不过事实上还有一种 \(\mathcal{O}(nm)\) 的做法。
发现瓶颈在于 \(k\) 的循环枚举，事实上这是可以优化的。我们发现在上面转移方程的第二种情况中，\(B[k] < B[j]\) 等价于 \(B[k] < A[i]\)，也就是这个条件的是否成立和 \(j\) 的取值无关。我们记满足 \(0 \le k < j, B[k] < A[i]\) 的所有 \(k\) 构成的集合记为 \(S(i, j)\)。发现有：
\[S(i, j +1) = \begin{cases} S(i, j) & B[j] \ge A[i]\\ S(i, j) \cup \{j\} & B[j] < A[i] \end{cases} \]因此枚举 \(j\) 时同时维护 \(S\) 中所有 \(k\) 对应的 \(f(i - 1, k)\) 的最大值即可。具体来说，设 \(g(i, j)\) 为 \(\max \limits _{k\in S(i, j)}\{f(i-1, k)\}\)，则有：
\[g(i, j +1) = \begin{cases} g(i, j) & B[j] \ge A[i] \or f(i - 1, j) \le g(i, j)\\ f(i - 1, j) & B[j] < A[i] \and f(i - 1, j) > g(i, j) \end{cases} \]用一个变量滚动地维护 \(g\) 即可。
记录方案直接 dp 时记录前驱。
/*
* @Author: crab-in-the-northeast
* @Date: 2022-11-06 00:59:09
* @Last Modified by: crab-in-the-northeast
* @Last Modified time: 2022-11-06 03:02:53
*/
#include <bits/stdc++.h>
inline int read() {
int x = 0;
bool flag = true;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
flag = false;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(flag)
return x;
return ~(x - 1);
}
const int maxn = 505;
const int maxm = 505;
int a[maxn], b[maxm];
int f[maxn][maxm];
int pre[maxn][maxm];
void pr(int x, int n) {
if (x == 0)
return ;
pr(pre[n][x], n);
printf("%d ", b[x]);
}
int main() {
int n = read();
for (int i = 1; i <= n; ++i)
a[i] = read();
int m = read();
for (int i = 1; i <= m; ++i)
b[i] = read();
a[0] = b[0] = -1;
for (int i = 1; i <= n; ++i) {
int k = 0;
for (int j = 1; j <= m; ++j) {
if (a[i] != b[j]) {
f[i][j] = f[i - 1][j];
pre[i][j] = pre[i - 1][j];
} else {
f[i][j] = f[i - 1][k] + 1;
pre[i][j] = k;
}
if (b[j] < a[i] && f[i - 1][j] > f[i - 1][k])
k = j;
}
}
int st = 0;
for (int i = 1; i <= m; ++i)
if (f[n][i] > f[n][st])
st = i;
printf("%d\n", f[n][st]);
pr(st, n);
puts("");
return 0;
}