AcWing 896. 最长上升子序列 II
本博客提供本题截图：
本题解析
本题用到了基础算法中的：二分法
数组q[i]存储的就是以长度为i的上升子序列中末尾元素最小的数
这里还用到了贪心的思想：以较小的数作为开头的数的子序列要比较大的数作为开头的子序列更好
二分需要查找：一个最大的小于等于当前数的数，找到之后会把这个数接到找到数的后面，并把长度 ++
AC代码
#include <iostream> #include <algorithm> using namespace std; const int N = 100010; int n; int a[N]; int q[N]; int main() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); int len = 0; for (int i = 0; i < n; i ++ ) { int l = 0, r = len; while (l < r) { int mid = l + r + 1 >> 1; if (q[mid] < a[i]) l = mid; else r = mid - 1; } len = max(len, r + 1); q[r + 1] = a[i]; } printf("%d\n", len); return 0; }
AcWing 897. 最长公共子序列
本题链接：AcWing 897. 最长公共子序列
本博客提供本题截图：
本题解析
这里按照是否要第i和第j个字母分成四大类，0代表不要，1代表要，即00代表的是不要第一个序列中的第i个字母和不要第二个序列中的第j个字母的最长公共子序列的长度
这里需要注意两点：
① f[i - 1, j]和f[i, j - 1]并不是我们所希望它表示的意思，拿f[i - 1, j]举例子，我们希望它表示的是不包含第一个序列中的第i个字母，包括第二个序列中的第j个字母的最长公共子序列的长度，但是按照我们给集合的定义，它表示的其实是在第一个序列的前i - 1个字母中出现，且在第二个序列的前j个字母中出现的子序列，这里需要注意 前j个字母中出现不一定第j个字母会出现，故其实我们的f[i - 1, j]所表达的意思涵盖范围更大一些，但是这并不会组织我们找到最大值，正因为我们表示的范围更大，故包括了我们需要的答案，只不过在计算过程中可能会有冗余重复
② 我们在进行写代码求Max的时候不需要加入f[i - 1, j - 1]，因为我们的f[i - 1, j]和f[i, j - 1]中包括了f[i - 1, j - 1]这种情况
AC代码
#include <cstdio> #include <algorithm> using namespace std; const int N = 1010; char a[N], b[N]; int f[N][N]; int main() { int n, m; scanf("%d%d", &n, &m); scanf ("%s%s", a + 1, b + 1); for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) { f[i][j] = max (f[i - 1][j], f[i][j - 1]); if (a[i] == b[j]) f[i][j] = max (f[i][j], f[i- 1][j - 1] + 1); } printf("%d\n", f[n][m]); return 0; }
