HDU 3415 Max Sum of MaxKsubsequence (单调队列)

Max Sum of Max-K-sub-sequence

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4573 Accepted Submission(s): 1653

Problem Description

Given a circle sequence A[1],A[2],A[3]......A[n]. Circle sequence means the left neighbour of A[1] is A[n] , and the right neighbour of A[n] is A[1]. Now your job is to calculate the max sum of a Max-K-sub-sequence. Max-K-sub-sequence means a continuous non-empty sub-sequence which length not exceed K.

Input

The first line of the input contains an integer T(1<=T<=100) which means the number of test cases. Then T lines follow, each line starts with two integers N , K(1<=N<=100000 , 1<=K<=N), then N integers followed(all the integers are between -1000 and 1000).

Output

For each test case, you should output a line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the minimum start position, if still more than one , output the minimum length of them.

Sample Input

4
6 3
6 -1 2 -6 5 -5
6 4
6 -1 2 -6 5 -5
6 3
-1 2 -6 5 -5 6
6 6
-1 -1 -1 -1 -1 -1

Sample Output

Author

shǎ崽@HDU

Source

HDOJ Monthly Contest – 2010.06.05

Recommend

lcy

最大的序列和，不过这个序列的长度不能超过k.

在i点时的最大和为sum[i]-min(sum[j]); i-k<=j<=i

枚举会超时，这里就用到了单调队列。

单调队列即保持队列中的元素单调递增（或递减）的这样一个队列，可以从两头删除，只能从队尾插入。

单调队列的具体作用在于，由于保持队列中的元素满足单调性，对于上述问题中的每个j，可以用O(1)的时间找到对应的s[i]。

（保持队列中的元素单调增的话，队首元素便是所要的元素了）。

维护方法：对于每个j，我们插入s[j-1]（为什么不是s[j]? 队列里面维护的是区间开始的下标，j是区间结束的下标），插入时从队尾插入。

为了保证队列的单调性，我们从队尾开始删除元素，直到队尾元素比当前需要插入的元素优

（本题中是值比待插入元素小，位置比待插入元素靠前，不过后面这一个条件可以不考虑），就将当前元素插入到队尾。

之所以可以将之前的队列尾部元素全部删除，是因为它们已经不可能成为最优的元素了，因为当前要插入的元素位置比它们靠前，值比它们小。

我们要找的，是满足(i>=j-k+1)的i中最小的s[i]，位置越大越可能成为后面的j的最优s[i]。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 const int INF=0x3f3f3f3f;
 8 const int maxn=200010;
 9 
10 int num[maxn],sum[maxn],q[maxn];
11 
12 int main(){
13 
14     //freopen("input.txt","r",stdin);
15 
16     int t,n,k;
17     scanf("%d",&t);
18     while(t--){
19         scanf("%d%d",&n,&k);
20         int i;
21         for(i=1;i<=n;i++)
22             scanf("%d",&num[i]);
23         for(i=1;i<=n;i++)   //前n项
24             sum[i]=sum[i-1]+num[i];
25         for(i=n+1;i<=n+k-1;i++) //首尾相接，尾部接上k-1位
26             sum[i]=sum[i-1]+num[i-n];
27         int head=0,rear=0;  //队首、队尾，在此队首为q[head],队尾为q[end]
28         int max=-INF;
29         int src,des;
30         for(i=1;i<n+k;i++){
31             int tmp=i-1;    //定长k的窗口的下界
32             while(head<rear && sum[q[rear-1]]>=sum[tmp])    //从尾向头入队，保证队列单调性，并丢弃无效值
33                 rear--;
34             q[rear++]=tmp;  //插入到end下一位
35 
36             while(head<rear && i-q[head]>k) //丢弃越界的值 ，保证队列长度不超过k
37                 head++; 
38             int id=q[head];
39             if(sum[i]-sum[id]>max){
40                 max=sum[i]-sum[id];
41                 src=id+1;
42                 des=i;
43             }
44         }
45         if(src>n)   //最后需要判断处理跨过n个数首尾的情况
46             src-=n;
47         if(des>n)
48             des-=n;
49         printf("%d %d %d\n",max,src,des);
50     }
51     return 0;
52 }