Codeforces 332B Maximum Absurdity（DP+前缀和处理）

题目链接：http://codeforces.com/problemset/problem/332/B

题目大意：
给你n个数和一个整数k，要求找到不相交的两个长度为k的区间，使得区间和最大，输出这两个区间的起点。
解题思路：
先计算前缀和，然后预处理出maxsum[i],maxsum[i]记录i~n最大的长度为k子段的和。
然后再去枚举即可。

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<vector>

 #include<string>

 #include<string.h>

 #include<cctype>

 #include<math.h>

 #include<stdlib.h>

 #include<stack>

 #include<queue>

 #include<set>

 #include<map>

 #define lc(a) (a<<1)

 #define rc(a) (a<<1|1)

 #define MID(a,b) ((a+b)>>1)

 #define fin(name)  freopen(name,"r",stdin)

 #define fout(name) freopen(name,"w",stdout)

 #define clr(arr,val) memset(arr,val,sizeof(arr))

 #define _for(i,start,end) for(int i=start;i<=end;i++)

 #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);

 using namespace std;

 typedef long long LL;

 const int N=5e6+;

 const LL INF64=1e18;

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 LL sum[N];      //记录前缀和

 LL maxsum[N]; //maxsum[i]记录i~n最大的长度为k子段的和

 int idx[N];      //idx[i]记录相应的i~n最大子段的起点 

 int main(){

     FAST_IO;

     int n,k;

     cin>>n>>k;

     for(int i=;i<=n;i++){

         cin>>sum[i];

         sum[i]+=sum[i-];

     }

     int lim=n-k+;

     for(int i=lim;i>=;i--){

         LL now=sum[i+k-]-sum[i-]; //now为i~i+k-1之和

         if(now>=maxsum[i+]){        //因为要保证答案字典序最小，所以下标往小的取

             maxsum[i]=now;

             idx[i]=i;

         }

         else{

             maxsum[i]=maxsum[i+];

             idx[i]=idx[i+];

         }

     }

     int st1=,st2=k+;

     LL mmax=sum[*k];

     for(int i=;i<=lim-k;i++){

         LL now=sum[i+k-]-sum[i-];

         if(now+maxsum[i+k]>mmax){ //maxsum[i+k]为i+k~n最大的长度为k的子段和

             mmax=now+maxsum[i+k];

             st1=i,st2=idx[i+k];

         }

     }

     cout<<st1<<" "<<st2<<endl;

     return ;

 }