272. 最长公共上升子序列
题意
熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。
小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。
小沐沐说，对于两个数列 A 和 B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。
奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。
不过，只要告诉奶牛它的长度就可以了。
数列 A 和 B 的长度均不超过 3000。
思路
f[i][j] = f[i - 1][j];
对于包含 a[i] 的 首先要满足公共子序列的性质 有a[i]==b[j] 但其无法直接用f[x][y] 这种形式表示 所以我们根据b 数组倒数第二个数字将上述集合进行划分：
即分成 以a 数组前i个数字和b 数组前 k (k∈[1,j−1])个数字组成 并且以]b[k] 结尾的 最长公共子序列
但是因为是最长公共上升子序列 所以要满足b[k]<b[j]
所以可以得到以下的代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 998244353 #define endl '\n' using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 3010; int n; int a[N], b[N]; int f[N][N]; // f[i][j] 表示 第一个数组前 i 个数字 和 第二个数组前 j 个数字 并且以b[j] 结尾的 // 最长公共上升子序列长度的最大值 int main() { cin >> 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]; // 不包含 a[i] if (a[i] == b[j]) { // 包含 a[i] 的条件为 a[i] == b[j] f[i][j] = max(f[i][j], 1); // 至少为1 因为当前已经有 a[i] == b[j] for (int k = 1; k < j; ++k) { // 从前 j - 1 个中找最大值 if(b[k] < b[j]) //因为是上升子序列 所以要保持严格递增关系 f[i][j] = max(f[i][j], f[i][k] + 1); } } } } int res = -1; for (int i = 1; i <= n; ++i) { res = max(res, f[n][i]); } cout << res << endl; return 0; }
for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { f[i][j] = f[i - 1][j]; // 不包含 a[i] if (a[i] == b[j]) { // 包含 a[i] 的条件为 a[i] == b[j] f[i][j] = max(f[i][j], 1); // 至少为1 因为当前已经有 a[i] == b[j] for (int k = 1; k < j; ++k) { // 从前 j - 1 个中找最大值 if(b[k] < b[j]) //因为是上升子序列 所以要保持严格递增关系 f[i][j] = max(f[i][j], f[i][k] + 1); } } } }
在这个循环中 当a[i]==b[j] 且b[k]<b[j]时 循环找到max(f[i][k]+1) 因为a[i]==b[j] 所以b[k]<a[i]
那么这个循环就跟j 没有任何关系了 可以放在for j 循环的外面
for (int i = 1; i <= n; ++i) { int maxn = 1; for (int j = 1; j <= n; ++j) { f[i][j] = f[i - 1][j]; // 不包含 a[i] if (a[i] == b[j]) f[i][j] = max(f[i][j], maxn); //包含 a[i] // 将下方的判断放在 f[i][j] 更新之后 可以保证f[i][j] 更新时 用到的 maxn 是前 j - 1 个数的 if (b[j] < a[i]) maxn = max(maxn, f[i][j] + 1); } }
完整代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 998244353 #define endl '\n' using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 3010; int n; int a[N], b[N]; int f[N][N]; // f[i][j] 表示 第一个数组前 i 个数字 和 第二个数组前 j 个数字 并且以b[j] 结尾的 // 最长公共上升子序列长度的最大值 int main() { cin >> 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 maxn = 1; for (int j = 1; j <= n; ++j) { f[i][j] = f[i - 1][j]; // 不包含 a[i] if (a[i] == b[j]) f[i][j] = max(f[i][j], maxn); if (b[j] < a[i]) maxn = max(maxn, f[i][j] + 1); } } int res = 0; for (int i = 1; i <= n; ++i) { res = max(res, f[n][i]); } cout << res << endl; return 0; }
