AcWing 272. 最长公共上升子序列
本博客给出本题截图：
AC代码
代码解释：f[i][j]代表所有在a[1 ~n]和b[1 ~ n]中都出现过，并且以b[j]结尾的公共上升子序列的最大值的集合
如果不包含a[i]的话那么
f[i][j] = f[i - 1][j];
如果包含a[i]的话，那么我们现在的公共上升子序列必然最后一位是a[i] (b[j])，那么我们开始根据倒数第二位去继续划分，进行状态转移，那么我们假设这个子序列的倒数第二位是b[k] (k < j)，当k == 0时证明没有倒数第二位，即当前子序列只有一个数，即maxv = 1，然后k从 1 开始遍历到 j - 1，注意在遍历的过程中，只有满足 b[k] < b[j]才可以更新maxv
if (a[i] == b[j]) { int maxv = 1; for (int k = 1; k < j; k ++ ) if (b[k] < b[j]) maxv = max(maxv, f[i - 1][k] + 1); f[i][j] = max(f[i][j], maxv); }
TLE版：
#include <iostream> #include <algorithm> using namespace std; const int N = 3010; int a[N], b[N], f[N][N]; 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 ++ ) { f[i][j] = f[i - 1][j]; if (a[i] == b[j]) { int maxv = 1; for (int k = 1; k < j; k ++ ) if (b[k] < b[j]) maxv = max(maxv, f[i - 1][k] + 1); f[i][j] = max(f[i][j], maxv); } } int res = 0; for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]); cout << res << endl; return 0; }
代码优化：三重循环，TLE 也不太意外，如何去优化呢？从第三重循环去下手，我们发现，对于我们遍历的每一个j，第三重循环都会重新遍历一遍1 ~ j - 1，这样显然是有很多重复在其中的，我们如果可以每次都把1 ~ j - 1中的最大值给存储起来，那么当我们j ++后，下一次该遍历1 ~ j的时候，只需要用这个最大值再去和j去比较即可，故我们把maxv放到一重循环中，然后来观察那个TLE代码：
if (a[i] == b[j]) { int maxv = 1; for (int k = 1; k < j; k ++ ) if (b[k] < b[j]) maxv = max(maxv, f[i - 1][k] + 1); f[i][j] = max(f[i][j], maxv); }
在这个代码中if (b[k] < b[j])可以替换为if (b[k] < a[i])，因为大前提是if (a[i] == b[j])，那么这个第三重的for循环就可以理解成在前j - 1中找到所有b[k] < a[i]的然后去更新，故当我们去掉第三重循环后可优化为：
if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
AC代码
#include <iostream> #include <algorithm> using namespace std; const int N = 3010; int a[N], b[N], f[N][N]; 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 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 (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1); } } int res = 0; for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]); cout << res << endl; return 0; }
