首页 > 其他 > 详细

hdu 3415"Max Sum of Max-K-sub-sequence"(单调队列)

时间:2019-04-29 21:21:39      阅读:133      评论:0      收藏:0      [点我收藏+]

传送门

 

题意:

  给出一个有 N 个数字([-1000 , 1000],N ≤ 105)的环状序列;

  让你求一个和最大的连续子序列,并记录起始点。

  要求这个连续子序列的长度小于等于K,加和相同的不同区间,输出起点最小的那组答案。

题解:

  因为序列是环状的,所以可以在序列后面复制一段(或者复制前k - 1个数字)。

  如果用sum[i]来表示复制过后的序列的前 i 个数的和;

  那么任意一个子序列[i..j]的和就等于s[ j ]-s[i-1]。

  对于每一个j,用s[ j ]减去最小的一个s[ i ](i ≥ j-k+1)就可以得到以 j 为终点长度不大于k的和最大的序列了。

  将原问题转化为这样一个问题后,就可以用单调队列解决了。

hdu 3415"Max Sum of Max-K-sub-sequence"(单调队列)

原文:https://www.cnblogs.com/violet-acmer/p/10792796.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!