![2023年12月13日总结](/img/20231213213954.webp)
2023年12月13日总结
![](https://picx.zhimg.com/v2-9e83e1fd23eccdb98450679841a3a4bc_xll.jpg)
总结
今天是 dp 专题。感觉好难。那就这样吧,开启新的一天吧!
决策单调性优化DP
四边形不等式优化 OI-WIKI
DP的决策单调性优化总结 –command_block
DP 优化方法大杂烩 –alex-wei
四边形不等式
考虑最简单的情形,我们要解决如下一系列最优化问题。
- 四边形不等式 :如果对于任意
均成立
若
满足四边形不等式,则问题 (1) 满足决策单调性。
常见优化方式:分治,二分队列。
「POI2011」Lightning Conductor 分治,头尾各来一遍就好。要注意,计算代价的时候不能向上取整,否则会破坏四边形不等式的性质!
「HNOI2008」玩具装箱 toy 区间分拆问题,内部满足四边形不等式外面也一定满足,写出来就会发现 f 消掉了。顺序递推,只能用二分队列来写了,虽然分治更好写。这道题显然可以斜率优化来做,但是也具有决策单调性的性质。
这道题也能用斜率优化写,因此顺便写了一遍斜率优化。
区间分拆问题
若
满足四边形不等式,则对于问题 (2) 成立 。
若
满足四边形不等式,则问题 (2) 的最优解 是关于 的凸函数。
然后就引出了 wqs 二分。
区间合并问题
- 区间包含单调性 :如果对于任意
均成立
则称函数
若
满足区间包含单调性和四边形不等式,则状态 满足四边形不等式。
若
满足区间包含单调性和四边形不等式,则问题 (3) 中最小最优决策 满足
例题:
Ciel and Gondolas 经典的决策单调性。这道题不用快读 TLE。好恶心。
wqs 二分
参看第三篇博客。
注意:保证最小情况下,段数最大最小值对二分过程有影响!三点共线的情况。
最小度限制生成树 wqs二分,但可以不用。数组开小了调了半天。伤心。
动态dp
还是参看第三篇博客。
可以用 矩阵乘法 描述转移方程,定义广义矩阵乘法:
只需要满足
常见广义矩阵乘法有
P4719【模板】动态 DP 动态树分治 树链剖分+
后记
dp 可真是有趣呢!使我使我……今天张贝还是没有来,zrj 也生病了,邓老师下午也离开了……呜呜呜。希望他们平安无事。
太伤心了,不写诗了。
喜报:我能去线下参加 WC 啦!
- 标题: 2023年12月13日总结
- 作者: 混氏新子
- 创建于 : 2023-12-13 23:10:39
- 更新于 : 2023-12-13 23:19:30
- 链接: https://blog.huasushis.cn/2023/2023年12月13日总结/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。