POJ 3415 Max Sum of Max-K-sub-sequence （线段树+dp思想）

Max Sum of Max-K-sub-sequenceTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5084    Accepted Submission(s): 1842


Problem DescriptionGiven 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. 
InputThe 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). 
OutputFor 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

46 36 -1 2 -6 5 -56 46 -1 2 -6 5 -56 3-1 2 -6 5 -5 66 6-1 -1 -1 -1 -1 -1

 
Sample Output

7 1 37 1 37 6 2-1 1 1

 
Authorshǎ崽@HDU 
SourceHDOJ Monthly Contest – 2010.06.05 
Recommendlcy 

题目大意：T 组数据，求 n 个数 连续子串的最大和是多少，子串要求长度不超过 k，以及这是个环形，如果多解，满足起点be最小，其次终点en最小

解题思路：枚举每个起点be，终点en一定是在 be<=en<=be+k-1 这个范围内，所以求这个范围内的连续最长和即可，可以用 sum[en] -sum[be-1] ，其中sum[x]表示前x个数的和，所以即选出 be<=en<=be+k-1这个范围内最大sum[i]，用线段树过了，但是rmq算法超时，郁闷！

线段树算法，AC

#include <iostream>#include <cmath>#include <cstdio>using namespace std;const int maxn=300005*2;int maxsum[maxn][20],minsum[maxn][20],flog[maxn],d[maxn],sum[maxn],n,k;void ini(){    int r=2,cnt=0;    for(int i=1;i<maxn;i++){        if(i<r) flog[i]=cnt;        else{            flog[i]=++cnt;            r=r<<1;        }    }}void input(){    scanf("%d%d",&n,&k);    for(int i=1;i<=n;i++){        scanf("%d",&d[i]);        d[i+n]=d[i];    }}void getrmq(){    for(int i=1;i<=2*n;i++){        sum[i]=sum[i-1]+d[i];        maxsum[i][0]=sum[i];        minsum[i][0]=sum[i];        }    for(int j=1;j<=flog[2*n];j++)    for(int i=1;i<=2*n;i++){        if(i+(1<<j)-1<=2*n){            maxsum[i][j]=max(maxsum[i][j-1],maxsum[i+(1<<(j-1))][j-1]);            minsum[i][j]=min(minsum[i][j-1],minsum[i+(1<<(j-1))][j-1]);        }    }}void computing(){    getrmq();    int ans=-(1<<30),be=1,en=1,l,r,x,tmp;    for(int i=1;i<=n;i++){        l=i,r=i-1+k,x=flog[r-l+1];        tmp=max(maxsum[l][x],maxsum[r-(1<<x)+1][x]);        if(tmp-sum[i-1]>ans){            ans=tmp-sum[i-1];            be=i;        }    }    for(int i=be;i<=be+k-1;i++){        if(sum[i]-sum[be-1]==ans){            en=i;            break;        }     }    printf("%d %d %d\n",ans,be>n?be-n:be,en>n?en-n:en);}int main(){    ini();    int t;    scanf("%d",&t);    while(t-- >0){        input();        computing();    }    return 0;}