例题及讲解
LIS
最长上升子序列 (Longest Increasing Subsequence，LIS)，一个数列中最长的单调递增的子序列。
例如 1 2 5 8 8 2 9 的 LIS 为 1 2 5 8 9，长度为 5.
模板题：Hdu 1257
某国发展出一种导弹拦截系统，它的第一发炮弹能够到达任意的高度，以后每一发炮弹都不能超过前一发的高度，给你一个导弹依此飞来的高度序列，请帮助计算一下最少需要多少套拦截系统.
$O(n^2)$ DP 解法
设 $ dp(i) $ 为前 $ i $ 个数以 $ i $ 结尾的 LIS 长度。
则 $ dp(i) = max(dp(j)+1|1 \leq j < i, a_j < a_i) $， $ a_i $ 为原数列。
初始化 $ dp(i) = 1 $，因为此时为一个数的最长上升子序列
代码(未编译)：
for (int i = 1; i <= n; ++i)
for (int j = 1; j < i; ++j) if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);
注意答案不是 $ dp(n) $，而是 $ max(dp(i)|1 \leq i \leq n) $
此做法时间复杂度为 $ O(n^2) $.
对于 Hdu 1257 的解法，我们只需要求出序列的最长上升子序列即可，因为有几个上升子序列就说明要开多少套拦截系统。最长上升子序列中必然不可能两个数用一个系统。
$O(nlogn)$ 数据结构优化 DP 解法
例题：Hdu 1950
$ T $ 组数据询问，每个询问包含一个 $ n $ 长序列，求 LIS。 ( $ n \leq 40000 $ )
原状态不能快速求出 LIS，我们试着换状态。
设 $ dp(x) $ 为以 $ x $ 值结尾的 LIS 长度。
则每次顺序扫描，$ dp(a_i) = max(dp(x)|x < a_i) $， $ a_i $ 为原序列
然后，我们观察 $ max(dp(x)|x < a_i) $，发现这个可以开一个数据结构维护 $ a_i $ 的值域来 $ O(logn) $ 求解。
具体解法是，顺序扫描 $ a_i $ ，每次在数据结构中查询值域区间 $ [0, a_i) $ (有可能有的题目值域会出现负数，所有数加上一个大正数即可，适当调整左端点的值)的最大值 $ x $，然后直接转移 $ dp(a_i) = x + 1 $。之后再将数据结构中 $ a_i $ 的位置修改为 $ dp(a_i) $。
参考代码 (使用线段树维护区间最大值)：
// 线段树维护区间最大值
int ans = 0;
for (int i = 1; i <= n; i++) {
dp[a[i]] = query(1, 0, MAXN, 0, a[i]) + 1;
ans = max(ans, dp[a[i]]); // 答案是所有的，不是一个 dp 值
update(1, 0, MAXN, a[i], dp[a[i]]);
}
此做法时间复杂度为 $ O(nlogn) $.
当然这个做法可以用树状数组来替换，代码会更简洁一些.
$O(nlogn)$ 贪心二分做法
我们开一个数组 $ b $，当前长度为 $ len $。
然后我们顺序把 $a$ 数组(原序列)的数加入数组 $ b $
如果当前 $ a_i > b_{len}$，那么直接将 $ a_i $ 插入 $ b $, 即 $ b_{len + 1} = a_i$
否则在 $ b $ 中找到一个数比 $ a_i $ 刚刚大一点的数，然后将这个位置用 $ a_i $ 替换掉。
此时 $ len $ 是 LCS 的长度。
假如我们有 2 5 4 8 3 4 5 这个序列，那么我们操作是
2 加入 $ b $, 此时 $ b = 2 $
5 加入 $ b $, 此时 $ b = 2, 5 $
4 加入 $ b $, 此时 $ b = 2, 4 $
8 加入 $ b $, 此时 $ b = 2, 4, 8 $
3 加入 $ b $, 此时 $ b = 2, 3, 8 $
4 加入 $ b $, 此时 $ b = 2, 3, 4 $
5 加入 $ b $, 此时 $ b = 2, 3, 4, 5 $
此时 $ len = 4 $ 为 LIS 长度。 注意 $ b $ 不是 LIS，
为什么是对的呢？
其实每次操作的 $ len $ 相当于当前找到的 LIS。每次如果当前数 $ a_i $ 比 $ b $ 中所有数都大，那么这个 $ a_i $ 可以对当前答案产生 $ 1 $ 的贡献。反之，就可以将这个数替换掉 $ b $ 中的某个数，使得 $ b $ 中的数保持单调递增但是整体尽量最小，以便于后面的数加入产生贡献。
参考代码
int n, a[40005], b[40005], len;
void clean() {
ms(b, 0), len = 0;
}
int solve() {
scanf("%d", &n);
clean();
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
b[1] = a[1], len = 1;
for (int i = 2; i <= n; ++i) {
if (a[i] > b[len]) b[++len] = a[i];
else {
int p = upper_bound(b + 1, b + 1 + len, a[i]) - b; // 注意 upper_bound
b[p] = a[i];
}
}
printf("%d\n", len);
return 0;
}
此做法时间复杂度为 $ O(nlogn) $.
LCS
最长公共子序列 (Longest Common Subsequence，LCS)，即两个或两个以上数列中最长的公共子序列。
例如 1 2 5 8 8 2 9 和 1 3 5 8 9 9 9 的 LCS 为 1 5 8 9
模板题：Hdu 1159
求两个字符串的最长公共子串。
$O(n^2)$ DP 解法
设 $ dp(i, j) $ 为第一个序列匹配到 $ i $，第二个序列匹配到 $ j $ 的 LCS 长度。
$ dp(i, j) = dp(i - 1, j - 1) + 1$，当且仅当 $ a_i=b_j $ (两个原序列)
$ dp(i, j) = max(dp(i - 1, j), dp(i, j - 1))$，当且仅当 $ a_i \ne b_j $
代码(未编译)：
for (int i = 1; i <= lena; ++i)
for (int j = 1; j <= lenb; ++j) {
if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
此做法时间复杂度为 $ O(n^2) $.
$O(nlogn)$ 解法
在所有数不相同或者排列的情况下能够完成 LCS 转化为 LIS 从而 $ O(nlogn) $ 时间复杂度求解，见下面综合中的 LCS 转 LIS。
如果有相同数也可以做，但是非常麻烦。
求 LCS 的方案
例题：luogu 2516
对给定的两个字符序列，求出他们最长的公共子序列长度，以及最长公共子序列个数。
第一问就是前面提到的 $ O(n^2) $的算法，主要看第二问
对于第二问，我们当前第一问的 DP 状态是 $ dp(i, j) $ 表示第一个串匹配到 $ i $，第二个串匹配到 $ j $ 的最长公共子序列。
然后我们再加一个数组 $ g(i, j) $ 表示第一个串匹配到 $ i $，第二个串匹配到 $ j $ 的最长公共子序列方案数。
对于这个数组的转移：
当 $ a_i = b_j $ 时，方案数加上$ g(i-1,j-1) $ 如果当前的 DP 值等于 $ dp(i-1, j) $ 或 $ dp(i, j-1) $，那么加上这些方案数，我们发现这个并不会重复
否则如果当前的 DP 值等于 $ dp(i-1, j) $ 或 $ dp(i, j-1) $，那么加上这些方案数。但是如果当前还等于 $ dp(i-1, j-1) $，说明 $ a_i , b_j $ 没做贡献，两个 LCS 均是从$i-1,j-1$的位置转移而来，减掉$ g(i-1,j-1) $即可。
注意开滚动数组，这种题目很容易就 MLE 爆 0 了
这种求方案数的方法很好，利用了一些容斥知识
代码：
for (int i = 0; i <= lb; ++i) g[cur ^ 1][i] = 1; //cur 表示滚动数组当前的位置，可以理解为 i。 cur ^ 1 为对称位置，可以理解为 i - 1。
for (int i = 1; i <= la; ++i) {
for (int j = 0; j <= lb; ++j) dp[cur][j] = 0, g[cur][j] = 0;
g[cur][0] = 1;
for (int j = 1; j <= lb; ++j) {
dp[cur][j] = max(dp[cur ^ 1][j], dp[cur][j - 1]);
if (a[i] == b[j]) {
dp[cur][j] = dp[cur ^ 1][j - 1] + 1;
g[cur][j] = g[cur ^ 1][j - 1];
if (dp[cur][j] == dp[cur ^ 1][j]) g[cur][j] = (g[cur][j] + g[cur ^ 1][j]) % MO;
if (dp[cur][j] == dp[cur][j - 1]) g[cur][j] = (g[cur][j] + g[cur][j - 1]) % MO;
} else {
if (dp[cur][j] == dp[cur ^ 1][j]) g[cur][j] = (g[cur][j] + g[cur ^ 1][j]) % MO;
if (dp[cur][j] == dp[cur][j - 1]) g[cur][j] = (g[cur][j] + g[cur][j - 1]) % MO;
if (dp[cur][j] == dp[cur ^ 1][j - 1]) g[cur][j] = (g[cur][j] - g[cur ^ 1][j - 1] + MO) % MO;
}
}
}
cur ^= 1;
}
printf("%d\n%d\n", dp[cur ^ 1][lb], g[cur ^ 1][lb]);
综合
LIS 转 LCS
LIS 问题在数字不重复情况下可以转化为 LCS 问题来求解。
具体方法是把原数组 $ a $ 增序排序后得到 $ b $，然后 $ a, b $ 的 LCS 长度就是原序列 $ a $ 的 LIS 长度。
例如 1 2 5 8 2 9 排序后为 1 2 2 5 8 9，两个序列 LCS 为 1 2 5 8 9
因为 $ LIS $ 是单调递增的，而排序后的数组也是单调递增的，所以两个串的 LCS 就是 LIS。
将问题互化了一下，两个算法都可以 $ O(n^2) $ 完成。可能在有的题目中会用到。
LCS 转 LIS
考虑所有数不相同或者排列的情况下能够完成 LCS 转化为 LIS 。
例题：Luogu 1439
给出$1-n$的两个排列$P_1$和$P_2$，求它们的最长公共子序列
这里只有排列，说明了什么？我们可以找到第二个序列每个元素在第一个序列的位置，那么我们用一个 map 来进行映射处理 (也就是找到“第二个序列每个元素在第一个序列的位置”)
例如：
3 4 2 1 5 和 1 3 4 5 2，“第二个序列每个元素在第一个序列的位置”(“对应序列”)序列为 4 1 2 5 3
然后我们可以观察发现 4 1 2 5 3 的 LIS 即为 LCS。
这个结论是正确的。
我们可以想想，“第二个序列每个元素在第一个序列的位置”序列是按照第二个序列的顺序来排的，也就是说这个序列第一个数 4 表示的是第二个序列第一个数在第一个序列的位置，而不是第二个数的。然后我们知道在第一个序列中求得的 LCS 子序列从左到右序号一定是递增的，所以在按第二个序列数排的“对应序列”中找 LIS 就可以找出两个序列的 LCS。因为第二个序列求得的 LCS 子序列从左到右序号也一定是递增的。
就相当于固定了第二个序列中元素的顺序，然后根据第一个序列中元素顺序来求一个交。
代码：
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), ma[a[i]] = i;//ma 为 map
for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
for (int i = 1; i <= n; ++i) b[i] = ma[b[i]];
tax[1] = b[1], len = 1;
for (int i = 2; i <= n; ++i) {
if (b[i] > tax[len]) tax[++len] = b[i]; else {
int p = lower_bound(tax + 1, tax + 1 + len, b[i]) - tax;
tax[p] = b[i];
}
}
printf("%d\n", len);
对于有重复数的，我们也能做，但是代码非常复杂。。
假如有 1 2 3 1 4 和 2 3 1 1 4，我们将“第二个序列每个元素在第一个序列的位置”(“对应序列”)序列的元素修改为一个集合，即比如第二个序列 1 对应两个位置，为 $(1, 4)$，然后根据这个来得到“对应序列”(上面例子的“对应序列”：2 3 1 4 1 4 5)，拆开集合的大括号继续做即可，注意可能有的数字对于空集的情况，代码太难写也没找到题就放这里读者有兴趣可以写写~
LCIS
顾名思义，LCIS 就是最长公共上升子序列。
例题：tyvj 1071
求两个序列的最长公共上升子序列。
我们可以设 $ dp(i, j) $ 为 $ a $ 序列匹配到 $ i $ 位置， $ b $ 序列匹配到 $ j $ 位置，以 $ b_j $ 结尾的 LCIS
参考代码：
for (int i = 1; i <= n; ++i) {
int k = 0;
for (int j = 1; j <= n; ++j) {
if (a[i] == b[j]) f[j] = max(f[j], f[k]+1), ans = max(ans, f[j]); else {
if (b[j] < a[i] && f[j] > f[k]) k = j;
}
}
}
一些题目
LIS 序列更改问题相关
1、例题：[Poj 3666]
给出一个数列$A_i$，求构造$B_i$使得$B_i$单调且$\sum_{i=1}^n |A_i - B_i|$最小, 只需要求出最小值。
2、例题：[Hdu 5256]
求将一个序列改成严格单调的最小次数。
先考虑不严格的情况。答案为$n-LIS$的长度
