lis

最长不下降子序列

定义
- 子序列 subsequence 可以不连续
- 子串 subarray 必须连续
四个相似的问题
- 最长不下降子序列 a[i] <= a[i+1]
- 最长上升子序列 a[i] < a[i+1]
- 最长不上升子序列 a[i] >= a[i+1]
  - 可以通过数组reverse 或者所有数字取相反数转化为最长不下降子序列
- 最长下降子序列 a[i] > a[i+1]
  - 可以通过数组reverse 或者所有数字取相反数转化为最长上升子序列
解法
- O(n^2) 直接动态规划，f[i] 表示 a[i] 结尾的最长不下降子序列的长度
- O(n log n) 二分搜索， f[i] 表示长度为i的最优解，最后一位最小是多少
- O(n log n) 数据结构， f[i] 表示最后一位为数值i的最优解，最后长是多少

最长不下降子序列

Longest Increasing Subsequence

简单的版本：对一个排列求最长不下降子序列

不下降，子序列中的 a[i-1] <= a[i]

3 2 1 4 5

f[i] is the LIS ending with a[i]
f[i] 表示以 a[i] 结尾的最长不下降子序列的长度

int ans = 0;
for (int i = 1; i <= n; i++)
{
    f[i] = 1;
    for (int j = 1; j < i; j++)
    {
        if (a[j] < a[i])
        {
            f[i] = max(f[i], f[j] + 1); // 对于一个i，这句话可能更新0次
        }
    }
    ans = max(ans, f[i]);
}

非常慢
very slow

时间复杂度 O(n^2)
基本没有用

3个方法

暴力

f[i] 表示以 a[i] 结尾的最长不下降子序列的长度

for (int i = 1; i <= n; i++)
{
for (int j = 1; j < i; j++)
{
if (a[j] <= a[i])
{
f[i] = max(f[i], f[j]);
}
}
f[i]++;
}
最终答案就是f数组中的最大值

按长度做动态规划

f[i] 表示到目前为止，长度为i的最长不下降子序列，最后一位最小是多少
f[i] the minimum value of the last element of IS with length i.

f[i] 一定是单调不减的
f[i] is no decreasing.

最后一位确定，长度越大越好
长度确定，最后一位越小越好

二分
求最长不下降子序列为例
f[i] 表示（到当前位置）长度为i，最后一位数值最小是多少
数值最小，可以使得之后能接的东西最多
https://github.com/wwwwodddd/Zukunft/blob/master/luogu/P1020.cpp

/*
1 4 7 2 5 8 3 6 9
x 表示无穷大
f[] = 
0 x x x x x x x x x // 初始
0 1 x x x x x x x x // 添加1之后
0 1 4 x x x x x x x
0 1 4 7 x x x x x x
0 1 2 7 x x x x x x
0 1 2 5 x x x x x x
0 1 2 5 8 x x x x x
0 1 2 3 8 x x x x x
0 1 2 3 6 x x x x x
0 1 2 3 6 9 x x x x // 添加9之后

0 1 2 3 4 5 
*/

每次添加一个新的数字a[i]
When we add a new number a[i]

对于最长不下降子序列
For Longest Non-deceasing Subsequence
找到位置p，f[p] > a[i] && f[p-1] <= a[i]，把f[p] = a[i]
Find p, such that f[p] > a[i] && f[p-1] <= a[i], do f[p] = a[i]
可以用 upper_bound 实现

对于最长上升子序列
For Longest Increasing Subsequence
找到位置p，f[p] >= a[i] && f[p-1] < a[i]，把f[p] = a[i]
Find p, such that f[p] >= a[i] && f[p-1] < a[i], do f[p] = a[i]
可以用 lower_bound 实现

最后答案就是最靠后的一个非无穷大的数字

实际实现过程中

不存储第一个0。
使用lower_bound / upper_bound
memset将f数组初始化为无穷大

如果存储第一个0，答案的长度是最后一个非x的下标，
如果不存储第一个0，答案的长度是第一个x的下标，

对于最长不下降子序列

*upper_bound(f, f + n, a[i]) = a[i]

对于最长上升子序列
找到位置p，f[p] >= a[i] && f[p-1] < a[i]，把f[p] = a[i]

*lower_bound(f, f + n, a[i]) = a[i]

int 4字节
memset(f, 0x3f, sizeof f);
f[0] = 0x3f3f3f3f = 1061109567

we can use binary search to find which one to update

按值做动态规划

f[i] 表示以数值 i 结尾的最长不下降子序列的长度

f[i] 表示最后一位是i，最大长度是多少
（可能需要离散化

对于每个 a[i] 相当于要求 f[1] f[2] ... f[a[i]] 的最值
需要数据结构支持

前缀求最大值
将一个位置改的更大

可以用线段树或树状数组或 map 优化
segment tree / binary indexed tree / STL map

一定满足询问一定是从1开始
一定越改越大
也可以树状数组优化

1 4 7 2 5 8 3 6 9

0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0
1 0 0 2 0 0 0 0 0
1 0 0 2 0 0 3 0 0
1 2 0 2 0 0 3 0 0
1 2 0 2 3 0 3 0 0
1 2 0 2 3 0 3 4 0
1 2 3 2 3 0 3 4 0
1 2 3 2 3 4 3 4 0
1 2 3 2 3 4 3 4 5

(0,1) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0)
(0,1) (1,1) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0)
(0,1) (1,1) (0,0) (0,0) (2,1) (0,0) (0,0) (0,0) (0,0) (0,0)
(0,1) (1,1) (0,0) (0,0) (2,1) (0,0) (0,0) (3,1) (0,0) (0,0)
(0,1) (1,1) (2,1) (0,0) (2,1) (0,0) (0,0) (3,1) (0,0) (0,0)
(0,1) (1,1) (2,1) (0,0) (2,1) (3,2) (0,0) (3,1) (0,0) (0,0)
(0,1) (1,1) (2,1) (0,0) (2,1) (3,2) (0,0) (3,1) (4,3) (0,0)
(0,1) (1,1) (2,1) (3,1) (2,1) (3,2) (0,0) (3,1) (4,3) (0,0)
(0,1) (1,1) (2,1) (3,1) (2,1) (3,2) (4,3) (3,1) (4,3) (0,0)
(0,1) (1,1) (2,1) (3,1) (2,1) (3,2) (4,3) (3,1) (4,3) (5,6)
求出了以每个位置结尾，最长上升子序列的长度，和最长上升子序列的方案数

1 4 7 2 5 8 3 6 9
有 6 个最长上升子序列
1 2 3 6 9
1 2 5 6 9
1 2 5 8 9
1 4 5 6 9
1 4 5 8 9
1 4 7 8 9

如果希望求出字典序第k大的解，那么需要倒着做
求出了以每个位置，最长上升子序列的长度，和最长上升子序列的方案数

（最长不下降子序列个数）
https://www.luogu.com.cn/problem/P5156
同时维护 (长度, 方案数)

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1376

first 长度
second 方案数

int ans = 0;
for (int i = 1; i <= n; i++)
{
    int t = 0;
    for (int j = 1; j <= a[i]; j++) // 上升 j < a[i]    不下降 j <= a[i]
    {
        t = max(t, f[j]);
    }
    f[a[i]] = t + 1; // 一定越改越大
    ans = max(ans, t + 1);
}

最终答案就是f数组中的最大值

f[i] the LIS ending with value i

for (int i = 1; i <= n; i++)
{
f[i] = find the LIS ending with [0, a[i]-1] + 1
update the data structure.
}

P1020

https://www.luogu.com.cn/problem/P1020
P1020 导弹拦截

65 8
155 3
158 7
170 6
207 2
299 5
300 4
389 1

389 207 155 300 299 170 158 65

389 300 299 170 158 65

https://en.wikipedia.org/wiki/Dilworth's_theorem

最小链覆盖 = 最长反链

每套系统拦截一个不上升的序列
最少需要几套系统

求最长上升子序列，在最长上升子序列中的任意2个导弹，都不能被同一个系统拦截

最长公共子序列和最长公共子串，是完全不一样的两个问题

https://www.luogu.com.cn/problem/P1439
P1439 【模板】最长公共子序列

关键点在于2个都是排列，总匹配位置

a[i] == b[j] (i, j)对数很少

3 2 1 4 5
1 2 3 4 5

通过替换（相同的数字替换相同的数字），使得第一个序列变成1 2 3 .. n
对于这个例子
1 2 3 4 5
3 2 1 4 5

3 2 1 4 5 这个排列非常重要

2 1 4 3 5
3 5 2 4 1
->
1 2 3 4 5
4 5 1 3 2

4 5 1 3 2 这个排列非常重要
在这个排列中的任意一个上升序列，都是原串的一个公共子序列

如果输入的数字不是排列，但是保证每个数字出现的次数都<=2次，怎么办？
1 2 3 1 2 3
1 1 2 2 3 3

a[i] == b[j] 生成所有(i, j)
(1, 1)
(1, 2)
(4, 1)
(4, 2)
(2, 3)
(2, 4)
(5, 3)
(5, 4)
(3, 5)
(3, 6)
(6, 5)
(6, 6)

得到了至多2n个(i, j)
从中选出一个子集，两维都是严格上升的
通过排序转化为1维的情况

第一维不严格上升，第二位不严格上升
第一维不严格上升，第二位严格上升
第一维严格上升，第二位不严格上升
第一维严格上升，第二位严格上升

排序按照第一维从小到大排序，如果第一维相等，那么第二维从大到小
(1, 2)
(1, 1)
(2, 4)
(2, 3)
(3, 6)
(3, 5)
(4, 2)
(4, 1)
(5, 4)
(5, 3)
(6, 6)
(6, 5)

2 1 4 3 6 5 2 1 4 3 6 5
对这个序列求最长上升子序列即可

一般的最长上升子序列，要求i < j && a[i] < a[j]

P2782 友好城市

https://www.luogu.com.cn/problem/P2782

构成 n 对 pair
按照 first 排序
sort them

7
2 6
4 2
9 8
10 3
15 12
17 17
22 4

对 second 求最长上升子序列
find the LIS of the second column

P6119 Why Did the Cow Cross the Road II

https://www.luogu.com.cn/problem/P6119
http://www.usaco.org/index.php?page=viewproblem2&cpid=718
Why Did the Cow Cross the Road II

6
1 2 3 4 5 6
6 5 4 3 2 1

1 2 3 4 5
匹配
5 4 3 2 1

2 3 4 5 6
匹配
6 5 4 3 2

对应的位置差值 <= d

f[i][j] 最长匹配子序列只用 a 的前 i 项， b 的前 j 项
f[i][j] longest from a[1..i] and b[1..j]

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= n; j++)
    {
        if (abs(a[i] - b[j]) <= 4)
        {
            f[i][j] = f[i-1][j-1] + 1;
        }
        else
        {
            f[i][j] = min(f[i-1][j], f[i][j-1]);
        }
    }
}

P3657 [USACO17FEB]Why Did the Cow Cross the Road II P

https://www.luogu.com.cn/problem/P3657

排列的最长公共子序列可以转化为最长不下降子序列

其实不需要是排列，只需要每个数字出现至多一次即可
其实不需要每个数字出现至多一次，只需要满足 s[i] == t[j] 的对数不太大（几倍的n即可）
在这个题目中，对于每个 a[i] 至多有 9 个 b[j] 满足 abs(a[i] - b[j]) <= 4
匹配的对数至多是 9n

生成这 9n 对，按 (先按first从小到大，如果first相等，按second从大到小) 排序，对 second 求最长上升子序列

At most 9n pairs
Generate all pairs, sort them, find LIS.

数据结构优化动态规划
如果需要求方案数，必须用这个方法
求最长不下降子序列为例
f[i] 最后一位是i的情况下，不下降子序列长度最长是多少
（如果需要求方案数）
g[i] 表示最后一位是i的情况下，达到了f[i]的长度，的方案数有多少个

i的范围可能很大？离散化

每次加入一个新的数字a[i]
f[a[i]] = max(f[1] ... f[a[i]]) + 1

（如果需要求方案数）
不是简单的max，
如果两个状态长度不同，返回长度较大的
如果长度相同，返回相同的长度，方案数相加

有2个做的方向

从前向后，可以知道以每个数字结束的方案数
从后向前，可以知道以每个数字开始的方案数

这个动态规划符合

一定越改越大
只问前缀
这两个条件

做法：

线段树（没有这2个条件都可以）
树状数组
用map维护一个上升的序列

https://www.luogu.com.cn/problem/P6119
Why Did the Cow Cross the Road II G
|a - b| <= 4 的LCS

方案数

方案数也可以用第二个方法，结合部分和实现

Luogu P1439
最长公共子序列转化为最长不下降子序列
然后用二分优化，有 $O(n \log n)$ 的做法。

最长不下降子序列

最长不下降子序列

相关题目

P1020

P2782 友好城市

P6119 Why Did the Cow Cross the Road II

P3657 [USACO17FEB]Why Did the Cow Cross the Road II P

方案数