动态规划

标签：pre right min 2s 柿子 动态 规划 left

拿出来写，我的 dp 真的要菜死了。

动态规划

也是大坑，待填。

斜率优化

推式子大题，推出柿子之后可以通过对柿子变换得到类似一次函数柿子，然后就可以扔到二维平面看做凸包，用二分/cdq/单调队列/数据结构等等东西维护，也可以用李超树偷懒硬搞，好像复杂度要多只老哥。

P4655 [CEOI2017] Building Bridges

简单题，写柿子:

\[f_i=\min\left \{ f_j+(h_i-h_j)^2 + pre_{i-1}-pre_j \right \} \]

其中 \(pre_i = \sum_{j=1}^{i} w_j\)，整理一下，写出：

\[f_i=h_i^2+pre_{i-1}+\min \left \{ f_j-2h_ih_j+h_j^2-pre_j\right \} \]

写斜率柿子，令 \(k=-2h_i\)，\(b=f_j+h_j^2-pre_j\)，则：

\[f_i=h_i^2+pre_{i-1}+\min \left \{ kh_i+b\right \} \]

现在就把后面 \(\min\) 里面的柿子看做一次函数，扔到李超树上取当 \(x=h_i\) 时的最小值即可。

code

P3195 [HNOI2008] 玩具装箱

推柿子:

\[f_i= \min \left \{ f_{j-1}+(i-j+\sum_{k=j}^{i} C_k - L)^2\right \} \]

记 \(s_j = \sum_{j=1}^{i} C_i+1\)，再变一下柿子，令 \(L\) 提前 \(+1\)：

\[f_i = \min \left \{ f_{j}+(s_i-s_{j}-L)^2\right \} \]

拆开无用量 :

\[f_i = s_i^2-2s_iL+L^2 + \min \left \{f_j+ s_j^2+2s_jL-2s_is_j\right \} \]

拿出后面的 \(\min\) 柿子，写成一次函数形式，\(b=f_j+s_j^2+2s_jL\)，\(k=-2s_j\)

\[f_i=s_i^2-2s_iL + L^2 + \min \left \{ ks_i+b\right \} \]

扔到李超树上求当 \(x=s_i\) 时的最小值就行了。

code

数据结构优化 dp

很多时候，我们的 dp 值可能由什么区间 \(\max\)，区间和之类的转移而来，这样我们就可以用数据结构来维护 dp 值，降低复杂度。

AT_dp_w Intervals

线段树优化板子题，这种区间问题我们的常见 trick 是仅当便利到右端点时才计算贡献，可以做到不重不漏，设计 \(f(i,j)\) 表示到第 \(i\) 个位置，上一个 \(1\) 在 \(j\) 位置的最大价值，首先有 \(f(i,i) = \max_{j=1}^{i} f(i-1,j)\)，然后我们每次遍历到一个右端点，只有 \(l_j \leq j\) 的位置才能有这个区间的贡献，所以我们固定右端点，每个位置开个 vector，便利区间修改即可，最后答案就是全部区间取 \(\max\)。

code

标签：pre,right,min,2s,柿子,动态,规划,left
From： https://www.cnblogs.com/Wei-Han-Fei/p/18377394