[BZOJ3156]防御准备

斜率优化DP裸题,具体详见斜率优化DP,写题解其实只是在打草稿…

设\( i < j < k \),在i处进行决策,f[i]表示在i处安装守卫塔时i-n这段所需花费。

若我们在i进行决策时选择j,花费为:

\[ f[i]=f[j]+\frac{(j-i)(j-i-1)}{2}+a[i] \]

我们可以把这个式子写成:

\begin{cases}
x(j)=f[j]+\frac{j(j-1)}{2}\\
y(i)=a[i]+\frac{i(i+1)}{2}\\
f[i]=x(j)+y(i)-ij
\end{cases}

若决策点k比j更优:

\[ x(k)+y(i)-ik < x(j)+y(i)-ij \]

\[ \frac{x(k)-x(j)}{k-j} < i \]

所以我们维护一个斜率单调减的队列即可。

P.S.:可在0处加一个点,费用为0,可以避免一些讨论

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注