女娲补天之最长上升子序列
最基础的数字三角形模型是在一个无序的序列中找出最长上升(下降同理)子序列。
如果是想要找到下降子序列,也只需要将起点和终点反一下求就好。
除了模板题以外,更需要能够从题目中抽象出最长上升子序列模型的能力。
基础DP:
时间复杂度:$O(n ^ 2)$
由于基础DP的时间复杂度较高,存在优化版本
刷题列表:
AcWing 895. 最长上升子序列
DP注意初始化,每个数最差也能以自己为开头和结尾构成一个序列,所以初始化为$1$
模板题
AcWing 896. 最长上升子序列 II
这题比较特殊,从DP发展而来,但采用了二分和贪心的思想。
如果想要上升子序列最长,那对每一组上升序列来说,在长度相同的情况下,如果末尾的值越小,就越有可能接上更多的数,反之末尾的值越大,就越难接上新的值。
因此想到贪心的思想,建立数组f
,f[i]
对应的元素是长度为i
的上升子序列中末尾元素最小的数。
比如可能有多个长度为$3$的上升子序列,f[3]
中只存储结尾最小的那一个数。
那么这个数组,一定是一个单调递增的数组。
假设如果f[6]
存储的值大于f[7]
存储的值,那么长度为7的上升序列的第六位一定小于f[6]
,f[6]
就不是长度为6的所有上升序列的最小值,与定义不符。
对于新的数,如何找到最合适的插入点?
按照贪心的思想,对于所有序列的结尾,需要找到一个最大的小于新的数的结尾,那么就用到二分去查找。
找到最大的(最靠近)小于新的数的结尾,更新的应该的是其数组位后一位的值。
比如新的数为9,f[6] = 7
,f[7] = 10
,更新的应该是f[7]
的值,因为长度为$6$的上升子序列再加上一个新元素,长度变为$7$了,所以需要更新f[7] = 9
最后数字的长度就是最长上升子序列的长度。
注意:这种方法虽然能够在大范围内求出最长上升子序列的长度,但是!!!!数组内存的不一定是正确的顺序,存在一定的局限性。
AcWing 1017. 怪盗基德的滑翔翼
模板题的变型
在本题中,需要找到以某个点为起点,求向任意方向的最长上升或者下降的子序列长度。
f[i]
的状态定义是:以第i
个数为结尾的最长上升子序列
g[i]
的状态定义是:以第i
个数为结尾的最长下降子序列
定义的是结尾,跟起点在哪没啥关系,所以只要从前到后求一遍f[i]
,再从后向前求一遍g[i]
,再去取最大值即可。
AcWing 1014. 登山
模板题的变型
本题不再单纯求一个最长的上升子序列,而是要求一个先上升再下降的最大长度的子序列模型。
也只要先从前到后求一遍上升子序列f[i]
,再从后向前求一遍g[i]
,再取二者相加再减一的最大值即可。
AcWing 482. 合唱队形
上题登山的变型
同样求一个先上升再下降的最大长度的子序列模型,只是这里需要输出的是总数减去求出的最大长度,剩下的就是需要出列的同学数量。
AcWing 1012. 友好城市
本题较难
如果按上岸的坐标从小到大枚举所有的可能情况
我们可以发现所有按照上岸的坐标从小到大枚举选择到的桥,其对应下岸的坐标也必然是从小到大的,否则就会出现冲突。
如下所示:
紫色表示该方案按照上坐标从小到大先选出来的桥。
红色表示该方案的下一座桥的下坐标不是从小到大的非法方案,蓝色表示下坐标是从小到大的合法方案。
对于所有的合法方案而言,上下两岸坐标都是递增的子序列。
那么只要保持一岸的坐标从小到大进行排序,然后对另一岸求最长递增子序列即可。
所以此题就变成了:上岸的坐标从小到大排序后,找出下岸坐标的最长上升子序列长度
AcWing 1016. 最大上升子序列和
之前是求最长上升子序列的数量,这里直接求上升子序列的和。
模板题中找到了合法的情况会+1
,这里只需要加上这个数就可以。
if w[i] > w[j]: f[i] = max(f[i], f[j] + w[i])
AcWing 897. 最长公共子序列
集合表示:$f[i][j]$表示$a$的前$i$个字母,和$b$的前$j$个字母的最长公共子序列长度
集合划分:以$a[i]$,$b[j]$是否包含在子序列当中为依据,因此可以分成四类:
①$a[i]$不在,$b[j]$不在
$max=f[i−1][j−1]$
②$a[i]$不在,$b[j]$在
看似是$max=f[i−1][j]$ , 实际上无法用$f[i−1][j]$表示,因为$f[i−1][j]$表示的是在$a$的前$i-1$个字母中出现,并且在$b$的前$j$个字母中出现,此时$b[j]$不一定出现,这与条件不完全相等,条件给定是$a[i]$一定不在子序列中,$b[j]$一定在子序列当中,但仍可以用$f[i−1][j]$来表示,原因就在于条件给定的情况被包含在$f[i−1][j]$中,即条件的情况是$f[i−1][j]$的子集,而求的是$max$,所以对结果不影响。
例如:要求$a,b,c$的最大值可以这样求:$max(max(a,b),max(b,c))$虽然$b$被重复使用,但仍能求出$max$,求$max$只要保证不漏即可。
③$a[i]$在,$b[j]$不在 原理同②,可以用$max=f[i][j - 1]$来进行求解
④$a[i]$在,$b[j]$在
$max=f[i−1][j−1]+1$
实际上,在计算时,①包含在②和③的情况中,所以①不用考虑
AcWing 1010. 拦截导弹
贪心 + DP
第一问:模板题
第二问:如果想要使用的导弹系统数量足够少,每一组系统能击落的导弹高度一定要相近,才能击落更多导弹。
比如已经分好了几组不同的系统,每个系统能击落的最后一颗导弹高度都不同,对于一个新导弹,尽量将其分配至能击落且高度与系统末尾高度最相近的组,也就是最小的大于新导弹高度的末尾高度。
于是想到贪心的思想,每次新的导弹高度,二分出最接近且大于新高度的最小值,并修改末尾的值,最后组数就是最少需要的数量。
(维护一个数组长度为cnt
的单调不减的q[N]
数组, q[N]
中每个元素维护的是当前以 q[i]
结尾的下降子序列)
仔细思考该分析方法,与大数据范围的最长上升子序列思考方式相似。
求一个序列的最大上升子序列的长度等价于求用非递增的子序列去覆盖一个序列的方案数。
所以甚至可以直接用两个普通DP,只需要修改一下条件就行。
AcWing 187. 导弹防御系统
贪心 + DP + DFS
相比于上一题的拦截导弹问题,本题需要先判断是进入上升序列还是下降序列,需要再套一层爆搜。
用up[k]
和down[k]
记录第k套上升(下降)系统目前所拦截的最后一个导弹。
dfs(u,v,t)
意味着已有u
个上升,v
个下降,正在处理第t
个数
本题用到了前两题的贪心策略,如果插入一个新数,对于上升序列而言,每次应放入末尾小于新数的所有情况中最大的一种,这样才不会浪费。
(假设现在要把一个数放入一个上升序列,那么一定是所有能放入的上升序列中,最后一个元素最大的那一个。)
下降序列同理,新的数要放入末尾大于新数的所有情况中最小的那种,也不会浪费。
对于每个新的数,都用二分去查找就行。
AcWing 272. 最长公共上升子序列
本题结合了最长公共子序列和最长上升子序列的状态定义
状态计算(对应集合划分):
首先依据公共子序列中是否包含a[i],将f[i][j]所代表的集合划分成两个不重不漏的子集:
- 不包含
a[i]
的子集,最大值是f[i - 1][j]
; - 包含
a[i]
的子集,将这个子集继续划分,依据是子序列的倒数第二个元素在b[]
中是哪个数:- 子序列只包含
b[j]
一个数,长度是$1$ - 子序列的倒数第二个数是
b[1]
的集合,最大长度是f[i - 1][1] + 1
- …
- 子序列的倒数第二个数是
b[j - 1]
的集合,最大长度是f[i - 1][j - 1] + 1
- 子序列只包含
不过就需要三重循环,优化有点不太理解
for i in range(1,n+1):
for j in range(1,n+1):
f[i][j] = f[i-1][j]
if a[i-1]==b[j-1]:
f[i][j] = max(f[i][j],1) # 前一个为空的情况,至少为1
for k in range(j):
if b[j-1]>b[k-1]:
f[i][j] = max(f[i][j],f[i-1][k]+1)