(递推)Maximum Absurdity CodeForces – 332B

题意：有n个数，找两个不相交的长度为k的连续子区间，使得两子区间内元素和为最大

思路：现对得到的数据进行处理，求出以每个位置为结尾的长度为k的区间和，以及在该点之后最大的区间和及其位置，再进行遍历

状态转移：dp[i] = max(dp[i+1], sum[i]);//逆序
显然，代码是抄的

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
#define LL long long
const int maxn = 2 * 1e5 +100;
LL n,k,a[maxn],sum[maxn],mx[maxn],pos[maxn],i;
int main()
{
    scanf("%lld%lld",&n,&k);
    for(i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        sum[i] = sum[i-1] + a[i];
        if(i>=k) sum[i] -= a[i-k];
    }
    for(i=n;i>=k;i--){
        if(sum[i]>=mx[i+1]){
            mx[i] = sum[i];
            pos[i] = i;
        }
        else{
            mx[i] = mx[i+1];
            pos[i] = pos[i+1];
        }
    }
    LL ans = 0,pos1 = 0,pos2 = 0;
    for(i=k;i<=n;i++){
        LL sm = sum[i] + mx[i+k];
        if(ans<sm){
            ans = sm;
            pos1 = i-k+1;
            pos2 = pos[i+k]-k+1;
        }
    }
    printf("%lld %lld\n",pos1,pos2);
    return 0;
}