【学习记录】24.02.19 DP 及其优化

· · 个人记录

DP及其优化

（DP明显都听不太懂qwq）

背包问题

01背包（逆序）、完全背包（正序）

略。

多重背包

二进制分组，可单调队列优化（没听见）。

P4141 消失之物

退背包。

扩展 求最优解

分治背包

P2371 [国家集训队] 墨墨的等式

同余最短路背包，状态优化。

P8392 [BalticOI 2022 Day1] Uplifting Excursion

没听见，放弃了。

P4322 [JSOI2016] 最佳团体

01分数规划、二分、树上背包。没听懂

区间DP

石子合并

断环为链。

BZOJ4380

没听。

[AGC026D] Histogram Coloring

前半部分没听见，讨论的是 h_i 相等的特殊情况。

设 dp_{l,r,k,0/1} 表示某区间高为 k，是否是 0 和 1 交替的方案数，按高度枚举求解。

笛卡尔树处理全局最小值，断开区间。

CF1372E Omkar and Last Floor

显然让 1 在列里更集中更优，即令 q_i 尽可能大。

设 f_{l,r} 表示区间最优且只考虑包含该区间的行时的答案，没怎么听懂。

P6563 [SBCOI2020] 一直在你身旁

设 f_{l,r} 表示该区间还需要多少代价。

则有f_{l,r}=\min_{k=l}^{r-1}{\max{f_{l,k},f_{k+1,r}}+a_k}

用单调队列优化，听不懂啊。好像还要线段树和二分。

四边形不等式

区间包含单调性，交叉优于包含。

P1912 [NOI2009] 诗人小G

放弃。

决策单调性

好了没了，下午全都放弃了（悲）