BZOJ 3437 小 P 的牧场

发布于 2017-06-12  185 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3437

题意:划分一个长度为 n 的序列,代价为某数学式子的值,代价最小....(貌似所有这种题都可以这样简述题意....


已经形成套路了...

考虑朴素 dp 式:

$$f_i=f_j+a_i+cost(j,i)$$

重点在于怎么\(O(1)\) 求出\(cost(j,i)\)

$$cost(j,i)=\sum_{k=j}^{i}(i-k)*b_k$$

预处理\(s_i\) 表示\(b_i\) 前缀和 \(sum_i\) 表示\(ib_i\) 前缀和

$$cost(j,i)=i(s_i-s_j)-(sum_i-sum_j)$$

令决策点 t<k 且 k 优于 t 整理式子化简可得

$$\frac{(f_k+sum_k)-(f_t+sum_t)}{s_k-s_t}< i$$

单调队列维护下凸壳

 


一个非常弱的准退役OIER