写在前面
讲师:(\_woxinchangdan\_)
内容:单调队列 数位(DP) 斜率优化 杂题选讲
单调队列
板子
单调队列优化多重背包
优化到 (O(nm))
-
限定最长长度的最大子段和
给出一个数列,选出其中连续非空且长度不超过M的一段,使得这一子段和最大。
枚举右端点,维护单调队列存储左端点
-
P4095 Eden的新背包问题
-
P2254 NOI2005 瑰丽华尔兹
决策集合先加入的先删除,都可以用单调队列优化
数位DP
通常用前缀和
若 (solve(x)) 求的是 ([0,x]) 则答案为 (solve(b)-solve(a-1))
若 (solve(x)) 求的是 ([0,x)) 则答案为 (solve(b+1)-solve(a))
两种写法:递推和记忆化搜索(今天讲的全是记搜)
预处理和答案无关,支持多次询问
-
不要62
考过经典题
-
P4127 同类分布
枚举各数位之和 (m) ,记录原数 (mod) (m) 的值在状态里(判断能否整除某个数)
-
P6218 [USACO06NOV] Round Numbers S
求 ([L,R]) 内二进制表示 (0) 的个数大于等于 (1) 的个数
状态里记录 (sum0,sum1) ,注意去掉前导零
-
恨7不成妻
求 ([L,R]) 内满足不是 (7) 的倍数,每一位都不是 (7) ,且各位数字之和不是 (7) 的倍数的数的平方和 (1 le T le 30,1 le L le R le 10^{18})
三个条件:
- 与 (7) 无关的数的个数:常规数位DP
- 与 (7) 无关的数的和:维护需要用到第一个个数。第 (pos) 位的贡献为 (i imes 10^{pos}+x) ( (x) 为后面符合条件的个数)
- 与 (7) 无关的数的平方和:(sum(i imes 10^{pos}+x)^2=sum i^2 imes 10^{2 imes pos}+sum 2 imes i imes 10^{pos} imes x+ sum x^2)
附课件里的图(
懒得推式子了)
可合并的状态要用记搜,重点在找什么样的状态是可合并的
斜率优化
(这里只放今天讲的部分,以后会专门发一篇博客讲斜率优化)
把题目中的条件转化为 (y=kx+b) 的形式
维护凸包(凸包上的点斜率具有单调性)
求 (max) :上凸包 求 (min) : 下凸包
X单调 k单调
单调队列维护凸包
每次加点时检查当前点和队首的点的斜率的关系
因为每个决策点只会进队出队一次,因此时间复杂度 (O(n))
-
P2900 [USACO08MAR]Land Acquisition G
有 (n) 块长方形土地,一次可以买很多块(顺序不限),花的价格是其中 (max{ length } imes max width) ,次数不限。求把所有土地都买完的最小花费。
将土地按照长度 (h) 从小到大排序
转移方程:
[f_i=min(f_j+h_i imes w_{i+1}) ]整理得:
[-f_j=h_i imes w_{j+1} -f_i ](X) 单调递减,(k>0) 且单调递增,单调队列维护上凸壳
-
P3195 玩具装箱
模板题不解释
X单调 k不单调
单调栈维护凸包
但是由于k的不确定性,我们不能弹掉队首,找答案时也不能直接取队首,必须保存完整的凸包,在凸包上二分求答案
X不单调 k不单调
平衡树 or CDQ维护凸包(在平衡树上查前驱后继)
杂题选讲
各种DP优化
P2476 [SCOI2008]着色方案
简化冗余状态
发现剩余油漆如果能涂的个数相同那么他们对答案的贡献相同,于是 (f[cnt1][cnt2][cnt3][cnt4][cnt5][last]) 记搜。
GYM102920D Electric Vehicle
两点之间距离为曼哈顿距离,油箱有大小限制,每个点加油有不同费用,最多可以中转10次,问最少花费。
简化冗余状态
最后一定是要么不加要么加满
换句话说每个点向另一个点只会转移两种状态,有用的状态和转移只有 (O(n^2)) 个
甚至不用DP,直接BFS即可
为啥写这题的人那么少
挂两篇题解链接:
P2473 奖励关
倒推决策 (期望DP和博弈论中常用倒推决策)
由 (1 le n le 15) 可知,用状压DP,将宝物状态压缩为 (s)
易想到用 (f_{i,s}) 表示到了第 (i) 轮,宝物状态为 (s) 的最大期望得分
但这是错的
为什么呢?
可能在第 (i) 轮无法到达状态 (s)
所以我们用倒推来解决, (f_{i,s}) 表示在第 (1) 轮到第 (i-1) 轮内宝物状态为 (s) ,第 (i) 轮到第 (k) 轮的最大期望得分
在转移方程中:
不取第 (k) 种宝物: (f[i+1][s])
取第 (k) 种宝物: (f[i+1][s|(1<<k-1)]+p_k)((1 le k le n))
若 (s) 的状态满足取第 (k) 种宝物的条件,有取或不取两种选择:
若 (s) 的状态不满足取第 (k) 种宝物的条件,只能不取:
这里求的是期望值, (f)覆盖了第 (i) 轮取了所有 (n) 种宝物的情况,所以每个状态算完后 (frac{f[i][s]}{n}) 即为题目中所求的期望平均值
由倒推的状态定义可知, (f[1][0]) 为最终答案
P4954 [USACO09OPEN]Tower of Hay G(干草堆)
倒推决策
先给出一个结论:底层最小时一定可构造出高度最高的方案
这是我不会证的神仙结论,所以这里引用dalao的证明:
任意取出一个能使层数最高的方案,设有CA层,把其中从下往上每一层最大的块编号记为Ai;任取一个能使底边最短的方案,设有CB层,把其中从下往上每一层最大的块编号记为Bi。显然A1>=B1,ACB<=BCB,这说明至少存在一个k属于(1,CB),满足Ak-1>=Bk-1且Ak<=Bk。也就是说,方案 A 第K 层完全被方案 B 第K 层包含。构造一个新方案,第K 层往上按方案 A,往下按方案 B,两边都不要的块放中间当第K 层。新方案的层数与 A 相同,而底边长度与 B 相同。证毕。 ——zkw
记 (sum) 为 (w) 的前缀和, (f) 为宽度, (g) 为高度
转移方程:
移项,得
因为 (i<j) , (sum) 是单增的,又因为要使转移尽可能合法,我们要尽量取最小的 (j) ,同时使 (sum_{j-1}-f_j) 尽可能大
即维护一个 (sum_{j-1}-f_j) 单增, (j) 单增的序列即可,单调队列优化DP
P5021 [NOIP2018 提高组] 赛道修建
一棵树,选一些链全部覆盖,使得最短链最长,求最小值最大
树上贪心
贪心+LCA+二分答案
对于整棵树从根开始DFS,从最底层开始,先判断可以选取哪些边组成长度 (ge mid)的赛道,每组成一条就 (check+1) ,等无法组成赛道时,就将未选中的边中最长的一条向上传递,等整棵树处理完成后比较组成赛道的个数是否 (ge m),即 (check) 是否 (ge m) ,二分更新答案
POI2009 GAS-Fire Extinguishers
一棵树,每个点至少被一个灭火器覆盖,每个灭火器可以最多覆盖s个点,灭火器最远可以覆盖距离为k的点,求出最少需要放置多少灭火器。
树上贪心
灭火器!!!
易知灭火器放在越靠上的位置越好
所以从下往上考虑,直到不得不放的时候再放
设 (f_{i,j}) 表示以 (i) 为根的子树中距离 (i) 为 (j) 的灭火器还有多少点能分配, (g_{i,j}) 表示以 (i) 为根的子树中距离 (i) 为 (j) 的点还有多少没有灭火
对于点 (x),若它的子树中存在与它距离为 (k) 的点没有灭火器,则点 (x) 一定要放置灭火器,因为 (x) 以上的点离那个点的距离都超过 (k)
考虑子树之间的情况,对于位于不同子树中的一个灭火器和一个点,如果它们的距离和为 (k) 或 (k-1) ,则这两点要消掉(距离一次加 (2) ,若这次不消,下次再往上跳一个点,距离变成 (k+1) ,不满足要求了
根节点特判,因为不能再往上跳了
GYM103049G Great Expectations
首尾关系
期望->倒推
记 (f_{i,j}) 表示刚好从第 (i) 关开始一直通关到最后,浪费了 (j) 秒情况下,破纪录还需要的最小期望时间。
可以失误的秒数为 (r-d-1) ,所以失误的时间不能超过这个数
如果 (j+d_i le r-n-1) ,有失败/不失败两种情况,失败又可分为重新开始/吃罚时继续走两种情况:
如果 (j+d_i > r-n-1) ,有失败/不失败两种情况,失败只能重新开始:
(f_{0,0}) 是最终答案
但是转移中要用到 (f_{0,0}) 呀,我们最后求的又是它,所以我们在转移的时候不知道 (f_{0,0}) ,怎么转移?
我们可以发现 (f_{0,0}) 是单调的,所以通过二分答案可求得 (f_{0,0})
path
在一个无向联通图中,每次随机选一条边联通,其他都不联通,如果面前有一条边联通,可以选择走也可以选择不走。问最优决策下期望多少次从 (1) 走到 (n) ((1 le n le 10^5))
首尾关系
期望(不过显然这个没法倒推)
一个位置的期望计算方式为:
所以即使我们知道了所有 (d_y) 的值,我们也无法直接求 (d_x) 的值
但是我们可以二分
画图(并没有)可得函数 (f_x(v)=frac{sum _{x
ightarrow y}min(v,d_y)}{deg_x}+frac{m}{deg_x}-v) 关于 (v) 单调,因此可以二分 (v) ,直到找到 (f_x(v)=0)
(来自课件)
P3622 [APIO2007]动物园
首尾关系
因为 每个小朋友站在大围栏圈的外面,可以看到连续的 5 个围栏 (目光短浅)·所以状压这 (5) 个即可,别的对这个小朋友没影响
设 (f_{j,s}) 表示 (i)~(i+4) 这五个围栏状态为 (s) 时,高兴的小朋友数
转移方程:
其中的 (g) 就是预处理出来的 (i)~(i+4) 这五个围栏状态为 (s) 时,高兴的小朋友数
(& 15) 是怎么来的?
(15(10)=01111(2))
所以它的作用为:取状压的五个数中的后四个,这四个就变成了下一组中的前四个
在环上,注意处理环
P4409 [ZJOI2006]皇帝的烦恼
首尾关系
写不动了qwq放一张课件上的图吧:
和 (a_1) 比较是为了最后比较第 (n) 个和第 (1) 个是不是不超过 (x) 个
CF1517F Reunion
补集转化
直接做显然不好做,因为啥也不知道
正难则反,将未参加的志愿者染成黑色,能完全覆盖(即所有志愿者距离 (r) 的点包括整棵树)的即为不合法方案,于是变成覆盖计数问题,统计不合法方案数以得到合法方案数
https://www.luogu.com.cn/paste/mafynxk2
[BALTIC2008] Elect
(n) 件物品,要使总体积尽量大,但去掉任何一个物品后总体积都小于 (frac{1}{2}) ,求最大总体积
排序后DP
为了保证合法,我们向不到 (frac{n}{2}) 个人的组合中加比这些党的最少人数都少的人进去,超过了 (frac{n}{2}) 则一定合法。即我们把 (n) 个党按人数从大到小排序,进行01背包,看最多能装多少。(注意只能从 (frac{n}{2}) 及以下转移)
(来自网络)
P4823 [TJOI2013]拯救小矮人
排序后DP
和国王游戏类似
贪心+背包
感性理解一下,高的人比矮的人要靠下放,因为他对别人的贡献更大;手长的人比手短的人要靠下放,因为他需要被补足的长度小,即需要的贡献少
所以综合起来考虑,按 (A_i+B_i) 从小到大排序
严谨一点的证明:
设剩下的高度和为 (sum) 得到:
即
所以
时,(x) 在 (y) 之前出去需要的 (sum) 更小,即 (x) 更可能在 (y) 之前出去
整理,得
P2876 [USACO07JAN]Problem Solving G
在状态中记答案
这个题很多种设状态的方法都可以
(f[i][j]) :解决了 (i) 个问题,花了 (j) 个月,第 (j+1) 个月已用的钱的最小值
转移方程:
统计答案:
P3537 [POI2012]SZA-Cloakroom
在状态中记答案
放课件:
CF311B Cats Transport
斜率优化
每只猫位置减去起点位置,问题变成选一些位置使得所有猫到这些点的总时间最小
设 (f_{i,j}) 表示第 (i) 个人第 (j) 个猫的最小代价, (sum_i=sum_{k=1}^{i} t_k)
则有:
代入 (y=Kx+b) ,得 (y=s_k+f_{i-1,k}) , (x=k) , (K=t_j) , (b=-t_jj+s_j+f_{i,j})
因为枚举的 (k) 是单增的, (t_j) 也是单增的,即 X单调,K单调,单调队列维护即可
https://www.luogu.com.cn/paste/rkxkzgb1
P4056 火星藏宝图
斜率优化
据说 (O(nm)) 吸氧可过,但是这里提供斜率优化到 (O(m^2)) 的做法
设 (f_{i,j}) 为走到 ((i,j)) 上的点的最大收益, (pos_i) 为第 (i) 列上当前能转移的点的最大行数, (x) 为当前点的行数
设 (j < k) ,且从 (k) 转移比从 (j) 转移优,得到:
就可以斜率优化了,注意横坐标相同时在一条水平线上,斜率设为 (-inf)
P5504 [JSOI2011] 柠檬
斜率优化
单调栈+二分(注意是单调栈不是单调队列!)
课件讲挺清楚的,直接放这里啦
肝了一天终于写完了 完结撒花!