6.6 KiB
一、题目描述
熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。
小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究 最长公共上升子序列 了。
小沐沐说，对于两个数列 A 和 B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。
奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。
不过，只要告诉奶牛它的长度就可以了。
数列 A和 B 的长度均不超过 3000。
输入格式
第一行包含一个整数 N，表示数列 A，B 的长度。
第二行包含 N个整数，表示数列 A。
第三行包含 N个整数，表示数列 B。
输出格式
输出一个整数，表示最长公共上升子序列的长度。
数据范围
1≤N≤3000,序列中的数字均不超过 2^{31}−1。
输入样例：
4
2 2 1 3
2 1 2 3
输出样例：
2
二、前导知识
状态表示
f[i]表示从第一个数字开始算，以a[i] 结尾 的最长的上升序列长度。(以a[i]结尾的所有上升序列中属性为最长的那一个)
状态计算
\left\{\begin{array}{l}
f[i] =1 & 默认值，前面没有比i小的，以a[i]结尾的最长个数是1 \\
f[i] = max(f[i], f[j] + 1) & 0 \le j<i \ \& \ a[j]<a[i]
\end{array}\right.
定义f[i][j]是a[]以i结尾，b[]以j结尾的 最长公共子序列长度，但没有说a[i]或者b[j]一定要出现在最长公共子序列当中！这个最长公共子序列，可能是a[]和b[]的一些前序组成的，a[i],b[j]也可能没有对结果产生贡献。
$ \large \left{\begin{array}{l} f[i][j]=f[i-1][j-1]+1 & a[i]=b[j] \ f[i][j]=max(f[i-1][j],f[i][j-1]) & a[i] \neq b[j] \end{array}\right. $
三、本题解法
闫氏DP分析法：(结合了LCS与LIS的状态表示的方法，可以很直接的发现二者的影子)
状态表示
-
f[i][j]—集合：考虑a中前i个数字，b中前j个数字 ，且当前以b[j]结尾的子序列的方案 -
f[i][j]—属性：max(所有符合条件方案的子序列长度)
状态转移
\large a_i \neq b_j考虑a数组中前i-1个数字，b数组中前j个数字 ，且当前以b[j]结尾的子序列的方案转移过来：
\large f[i][j]=max(f[i][j],f[i−1][j])\large a_i = b_j考虑a数组中前i-1个数字，b数组中前k个数字 ，且当前以b[k]结尾的子序列的方案转移过来：
\large f[i][j]=max(f[i][j],f[i−1][k]+1),k∈[0,j−1],a_i=b_j,b_j>b_k按上述思路实现，需要三重循环：
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
int a[N], b[N];
int f[N][N];
int res;
// 通过了 10/13个数据
// O(n^3)
int main() {
int n;
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++)
for (int j = 1; j <= n; j++) {
// ① 二维DP打表的一般套路，都是可以直接从上一行继承的
// ② 从题意出发，就是a中前i个数字，b中前j个数字，且以b[j]结尾的子序列中长度最大的
// 那么，a中多整出一个数字来，最起码也是f[i-1][j]的值，不能更小
f[i][j] = f[i - 1][j];
// ③ 如果恰好 a[i]==b[j],那么就可以发生转移
if (a[i] == b[j]) {
int mx = 1; // 最起码a[i]==b[j]，有一个数字是一样嘀~
// f[i-1]是肯定的了，问题是b的前驱在哪里？需要枚举1~j-1
for (int k = 1; k < j; k++)
if (b[j] > b[k]) // 需要上升
// 找出公共且最长的
mx = max(mx, f[i - 1][k] + 1);
// 更新答案
f[i][j] = max(f[i][j], mx);
}
}
int res = 0;
// a数组肯定是火力全开到n就行，b数组中的位置就需要枚举了
for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
printf("%d\n", res);
return 0;
}
### 四、优化
Q:朴素办法超时(10/13)，如何优化？
观察到，对于第二种状态转移：f[i][j]=max(f[i][j],f[i−1][k]+1) \ k∈[0,j−1],a_i=b_j,b_j>b_k
每次用到的 状态 都是第 i - 1 个阶段的
因此我们可以用一个变量，存储上一个阶段的能够接在 a[i] 前面的最大的状态值
最终答案枚举子序列结尾取最大值即可。
实现代码O(N^2)
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
int a[N], b[N];
int f[N][N];
int res;
// O(n^2)
int main() {
int n;
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 mx = 1;
for (int j = 1; j <= n; j++) {
f[i][j] = f[i - 1][j];
if (a[i] == b[j]) f[i][j] = mx;
if (a[i] > b[j]) mx = max(mx, f[i - 1][j] + 1);
}
}
for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
printf("%d\n", res);
return 0;
}
五、空间优化
本题还可以继续优化成一维数组，但在现实中意义不大。
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
int a[N], b[N], 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 maxv = 1;
for (int j = 1; j <= n; j++) {
if (a[i] == b[j]) f[j] = max(maxv, f[j]);
if (a[i] > b[j]) maxv = max(f[j] + 1, maxv);
}
}
int res = 0;
for (int i = 1; i <= n; i++) res = max(res, f[i]);
cout << res << endl;
return 0;
}