斜率优化

例题引入

「HNOI2008」玩具装箱

有 \(n\) 个玩具，第 \(i\) 个玩具价值为 \(c_i\)。要求将这 \(n\) 个玩具排成一排，分成若干段。对于一段 \([l,r]\)，它的代价为 \((r-l+\sum_{i=l}^r c_i-L)^2\)。其中 \(L\) 是一个常量，求分段的最小代价。

\(1\le n\le 5\times 10^4, 1\le L, c_i\le 10^7\)。

朴素的 DP 做法

令 \(f_i\) 表示前 \(i\) 个物品，分若干段的最小代价。

状态转移方程：$f_i=\min_{j

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Marcythm, hsfzLZH1, abc1763613206, greyqz, Ir1d, billchenchina, Chrogeek, Enter-tainer, StudyingFather, MrFoodinChina, luoguyuntianming, sshwy, wood3
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用