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

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

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

a * (b + c) + b * c

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

(a + b) * c +[……]

Read more

bzoj 4518: [Sdoi2016]征途 DP 斜率优化

原式可以化简成  m * sum(xi^2)(i = 1 – > m) – sum(xi)(i = 1 -> m)

如果你很好奇为什么可以化成这个形式,请注意一个事实。x的平均值*m是等于所有的和。

我们发现我们无非就是求最小的sum(xi^2)(i = 1 -> m)[……]

Read more

bzoj 1597: [Usaco2008 Mar]土地购买 斜率优化DP

开始直接在单调队列里加入一个1。后来一直WA。后来发现,需要在单调队列内加入一个0,保证任何时候都有可能从头开始。

f[i] 表示[1,i]的最小代价。