bzoj 3675: [Apio2014]序列分割 斜率优化

首先你要发现这题有个奇妙的性质,就是说当你一个切割方案确定下来,你切的先后的顺序对最终的答案没有任何影响。

做一个简单的证明,假设a b c我们考虑先切a右侧,再切b右侧答案是

a * (b + c) + b * c

先切b右侧,再切a右侧,答案是

(a + b) * c + a * b

我们发现两个式子化简完都是a * c + b * c + a * b,显然没啥区别/-v-/

这样子这就是一个非常简单合理的序列DP了。

f[i][j]表示前j个数切i刀的最大收益。

f[i][j]=max{f[i1][k]+sum[k]×(sum[j]sum[k])}

然后我们推一下式子就可以了。

打公式好麻烦。贴个不错的链接:http://www.cnblogs.com/Tunix/p/4458648.html

发表评论