斜率优化

例题引入

「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

---

本页面最近更新：2024/6/22 01:07:37，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：sshwy, GavinZhengOI, StudyingFather, Ir1d, Marcythm, mgt, Enter-tainer, luoguyuntianming, ouuan, abc1763613206, BackSlashDelta, billchenchina, Chrogeek, ChungZH, fps5283, greyqz, GreyTigerOIer, Henry-ZHR, hsfzLZH1, Kaiser-Yang, Konano, Luckyblock233, MrFoodinChina, NachtgeistW, nanmenyangde, wood3, Xeonacid, 代建杉
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用