[BZOJ3156]防御准备(动态规划,斜率优化)

发布于 2018-04-08  184 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3156]防御准备(动态规划,斜率优化)

Description

[BZOJ3156]防御准备(动态规划,斜率优化)

Tag

动态规划,斜率优化

解决思路

设F[i]表示前i个检查点并且强制在i这里设置一个检查点的最小花费,那么有
\[F[i]=min(F[j]+(i-j)*(i-j-1)/2)+Cost[i]\]
里面是一个可以斜率优化的式子,化成斜率形式
\[F[j]+\frac{1}{2}j^2+\frac{1}{2}j=ij-Cost[i]+F[i]+\frac{1}{2}i-\frac{1}{2}i^2\]
那么现在的任务就是要最小化截距,由于斜率和i都是递增的,所以维护一个下凸壳,用单调队列维护。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3156]防御准备(动态规划,斜率优化)


HNCJ OIer