BZOJ 2006 [NOI2010] 超级钢琴


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

题意:选出 k 个不同连续子序列,满足这些子序列的和的和最大。


五元组 (sum,x,l,r,id) 表示目前左端点为 x,右端点在 [l,r] 区间内,最大子序列和为 sum,在下标 id 处取到。

用一个堆维护,区间最值处理前缀和后可以 st 表求。

每次取出堆顶,分裂成 [l,id-1],[id+1,r] 两个区间

 

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

转载:转载请注明原文链接 - BZOJ 2006 [NOI2010] 超级钢琴


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

标签: , , ,