HDu 3415 Max Sum of Max-K-sub-sequence単調キュー.
10901 ワード
Max Sum of Max-K-sub-sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5335 Accepted Submission(s): 1939
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
7 1 3
7 1 3
7 6 2
-1 1 1
Author
shǎ子@HDU
Source
HDOJ Monthly Contest – 2010.06.05
Recommend
lcy | We have carefully selected several similar problems for you:
3423
3417
3418
3419
3421
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5335 Accepted Submission(s): 1939
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
7 1 3
7 1 3
7 6 2
-1 1 1
Author
shǎ子@HDU
Source
HDOJ Monthly Contest – 2010.06.05
Recommend
lcy | We have carefully selected several similar problems for you:
3423
3417
3418
3419
3421
1 #include<iostream>
2 #include<stdio.h>
3 #include<cstdlib>
4 #include<cstring>
5 #include<cstdlib>
6 using namespace std;
7
8 int a[200004],s[200004];
9 int head,tail,len,n,k;
10 typedef struct
11 {
12 int sum;
13 int s,e;
14 }Queue;
15 Queue q[200004],tom,tmp;
16
17 void Init()
18 {
19 int i;
20 for(i=1;i<=n;i++)
21 scanf("%d",&a[i]);
22 len=n+k;
23 for(i=n+1;i<=len;i++)
24 a[i]=a[i-n];
25 for(s[0]=0,i=1;i<=len;i++)
26 s[i]=a[i]+s[i-1];
27 n=n+k;
28 len=len-k;
29 }
30 int main()
31 {
32 int T,i;
33 scanf("%d",&T);
34 while(T--)
35 {
36 scanf("%d%d",&n,&k);
37 Init();
38 head=0;tail=0;
39 tom.sum=s[1];tom.s=1;tom.e=1;
40 q[0]=tom;
41 for(i=2;i<=n;i++)
42 {
43 tmp.sum=s[i];
44 tmp.s=1;
45 tmp.e=i;
46 while( head<=tail && q[tail].sum>tmp.sum ) tail--;
47 q[++tail]=tmp;
48 while( head<=tail && q[head].e+k<tmp.e ) head++;
49
50 if(tmp.sum-q[head].sum>tom.sum && tmp.e!=q[head].e)
51 {
52 tom.sum=tmp.sum-q[head].sum;
53 tom.s=q[head].e+1;
54 tom.e=tmp.e;
55 }
56 else if( i<=k && tmp.sum>tom.sum)
57 {
58 tom=tmp;
59 }
60 }
61 printf("%d",tom.sum);
62 if( tom.s>len ) tom.s-=len;
63 if( tom.e>len ) tom.e-=len;
64 printf(" %d %d
",tom.s,tom.e);
65 }
66 return 0;
67 }