总结

今天是 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 二分

参看第三篇博客。

注意：保证最小情况下，段数最大最小值对二分过程有影响！三点共线的情况。

P2619 [国家集训队] Tree I 典题。

最小度限制生成树 wqs二分，但可以不用。数组开小了调了半天。伤心。

动态dp

还是参看第三篇博客。

可以用 矩阵乘法 描述转移方程，定义广义矩阵乘法：

只需要满足具有结合律，且对有分配律，则存在结合律。

常见广义矩阵乘法有卷积，卷积，卷积。

P4719【模板】动态 DP 动态树分治 树链剖分+矩阵维护。

后记

dp 可真是有趣呢！使我使我……今天张贝还是没有来，zrj 也生病了，邓老师下午也离开了……呜呜呜。希望他们平安无事。

太伤心了，不写诗了。

喜报：我能去线下参加 WC 啦！