概览
求两个序列的最长公共上升子序列
题解
- 集合表示f[i, j]: 所有由第一个序列的前i个字母,第二个序列的前j个字母, 且以b[j]结尾的构成的公共子序列,Max
> 注意这里要加条件 - 状态计算:
- 所有包含a[i]的公共上升子序列 a[i]==b[j]
> 按照倒数第2类划分, 序列倒数第1个数时null, b[1], b[2], .., b[j-1]
> 进行枚举 f[i,k] + 1 因为b[j]大于,所以实际上就是 - 所有不包含a[i]的公共上升子序列 f[i-1, j]
- 所有包含a[i]的公共上升子序列 a[i]==b[j]
代码
O(n^3)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3010;
int n;
int a[N], b[N];
int f[N][N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++) scanf("%d", &b[i]);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++) {
f[i][j] = f[i - 1][j];
if (a[i] == b[j]) {
f[i][j] = max(f[i][j], 1);
for (int k = 1; k < j; k ++)
if (b[k] < b[j]) f[i][j] = max(f[i][j], f[i][k] + 1);
} // else 只剩下一种
}
int res = 1;
for (int i = 1; i <= n; i ++) res = max(res, f[n][i]);
printf("%d\n", res);
return 0;
}
代码的优化实际上就是对代码做等价变形
O(n^2)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3010;
int n;
int a[N], b[N];
int f[N][N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++) scanf("%d", &b[i]);
for (int i = 1; i <= n; i ++) {
int maxv = 1;
for (int j = 1; j <= n; j ++) {
f[i][j] = f[i - 1][j];
if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
if (b[j] < a[i]) maxv = max(maxv, f[i][j] + 1);
}
}
int res = 1;
for (int i = 1; i <= n; i ++) res = max(res, f[n][i]);
printf("%d\n", res);
return 0;
}