标签：pre 2v min 2kv 玩具 iv HNOI2008 装箱 dp

前言

终于进入新专题了家人们

列举一下还要补的专题

1. 矩阵快速幂
2. 组合数学
3. \(\rm{sos\ dp}\)

不过先不管了, 除了复习, 大部分时候总要向前看的嘛

考试的时候带着耳塞, 不带感觉好吵啊, 但是一直带着会神经衰弱的, 所以只能尝试集中注意力

思路

首先转化题意

给定 \(n\) 条线段, 第 \(i\) 条线段的长度为 \(C_i\) , 我们要将这些线段分开, 其中一个分段 \([L, R]\) 的花费为 \(cost = (R - L + \sum_{i = L}^{R} C_i - W)^2\) , 求最小的花费之和

容易想到 \(\rm{dp}\) , 令 \(dp_{i}\) 表示考虑到第 \(i\) 条线段的最优花费
容易找到转移

\[\begin{align*} dp_i & = \min_{j \in [0, i]} dp_j + (i - j - 1 + pre_i - pre_j - W)^2 \\ & = \min_{j \in [0, i]} dp_j + [(pre_i + i) - (pre_j + j) - (W + 1)]^2 \\ 令 k &= (W + 1), v_i = pre_i + i \\ & = \min_{j \in [0, i]} dp_j + (v_i - v_j - k)^2 \\ & = \min_{j \in [0, i]} dp_j + (v_i - v_j)^2 + k^2 - 2k(v_i - v_j) \\ & = k^2 + \min_{j \in [0, i]} dp_j + (v_i^2 + v_j^2 - 2v_iv_j) - 2kv_i + 2kv_j \\ & = -k^2 + \min_{j \in [0, i]} dp_j + (v_i^2 - 2kv_i + k^2) + (v_j^2 + 2kv_j + k^2) - 2v_iv_j \\ & = -k^2 + \min_{j \in [0, i]} dp_j + (v_i- k)^2 + (v_j + k)^2 - 2v_iv_j \\ & = v_i^2 - 2kv_i + \min_{j \in [0, i]} dp_j + (v_j + k)^2 - 2v_iv_j \\ \end{align*} \]

考虑最终的柿子

\[dp_i = v_i^2 - 2kv_i + \min_{j \in [0, i]} dp_j + (v_j + k)^2 - 2v_iv_j \]

考虑

\[\min_{j \in [0, i]} dp_j + (v_j + k)^2 - 2v_iv_j \]

你发现 \(v_iv_j\) 这样的形式, 考虑斜率优化
先不管 \(v_i^2 - 2kv_i\) , 我们写出柿子

\[dp_i = \min_{j \in [0, i]} dp_j + (v_j + k)^2 - 2v_iv_j \]

拆掉 \(\min\)

\[dp_i = dp_j + (v_j + k)^2 - 2v_iv_j \]

\[\Downarrow \]

\[dp_j + (v_j + k)^2 = 2v_iv_j - dp_i \]

套路的, 令 \(x = v_j, y = dp_j + (v_j + k)^2, k = 2v_i, b = -dp_i\)
柿子转化为

\[y = kx + b \]

考虑其性质满足 \(k, x\) 单调递增, 我们简单的运用斜率优化, 使得 \(b\) 最大

\[{dp_i}_{\min} = -b_{\max} + v_i^2 - 2kv_i \]

考虑实现,
由于 \(k, x\) 的单增, 我们考虑使用单调队列维护上凸包
单调队列维护点即可

实现

框架

直接按照上述内容实现即可

代码

等一下, 先把今天题补了

总结

常见的 \(\rm{dp}\) 状态设计

优化不来可以考虑继续研究柿子

常见的斜率优化, 拆柿子能力史诗级提升

标签：pre,2v,min,2kv,玩具,iv,HNOI2008,装箱,dp
From： https://www.cnblogs.com/YzaCsp/p/18662331