HDU3415 (Max Sum of Max-K-sub-sequence)[前缀和，单调队列]

发表于 | 更新于 | | 阅读次数：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3415

这题乍一看是区间最大子段和加上了长度的限制。
维护一个前缀和b[n]，枚举i，对于当前i，显然最优解是b[i]-min(b[l])，其中i-k<= l <=i-1。
此时只需要能快速找出b[l]即可。
考虑每次只需要找到满足位置要求（l的要求）的之前一段到当前位置的最小值，我们可以用单调队列来维护这个最小值。
这里维护一个单增的单调队列，每次取最小值时从队首找到第一个符合位置要求的值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100009;
int n,k;
int T;
int a[maxn*2];
int b[maxn*2];
int q[maxn*2];
int p[maxn*2];
int l,r;
int main() {
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&n,&k);
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(q,0,sizeof(q));
		memset(p,0,sizeof(p));
		l=r=0;
		for(int i=1;i<=n;i++) scanf("%d",a+i),a[i+n]=a[i];
		for(int i=1;i<=2*n;i++) b[i]=b[i-1]+a[i];
		int mx=-2147483648;
		int mxl=0,mxr=0;
		for(int i=1;i<=2*n;i++) {
			while(l<r && b[i-1]<q[r-1]) r--;
			q[r]=b[i-1];
			p[r++]=i-1;
			while(l<r && p[l]<i-k) l++;
			if(b[i]-q[l]>mx) {
				mx=b[i]-q[l];
				mxl=p[l]+1;
				if(mxl>n) mxl-=n;
				mxr=i;
				if(mxr>n) mxr-=n;
			}
		}
		printf("%d %d %d\n",mx,mxl,mxr);
	}
}