BZOJ 3437 小 P 的牧场


题目链接: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$$

单调队列维护下凸壳

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 3437 小 P 的牧场


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,