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

hdu 3415
题意:给出n个整数,是一个环(也就是a[n]右边是a[1])求一段长度不超过k的数使得和最大,问最大和是多少并给出这段数的位置。

思路:为了处理环,先把n个数复制一下就好,然后求前缀和sum[i]

由于区间[l,r]的和可以用前缀和表示为sum[r]-sum[l-1]

因此在区间长度小于等于k的前提下,我要求sum[r]-sum[l-1]的最大值,如果我们考虑把端点r固定,那么就是要求[l-1,r-1]中的sum的最小值。

因此我们考虑用单调队列来维护sum[i-k]到sum[i-1]的最小值。

我们的做法是:枚举区间右端点i,同时用单调队列维护i之前的k个数[i-k,i-1]的最小值。

由于要求“If there are more than one result, output the minimum start position, if still more than one , output the minimum length of them.”,因此从后面出队的判断条件是严格的sum[dq.back()]>sum[i-1]

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz