codeforces B.Maximum Absurdity 解题报告

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

题意：在一个序列中，在所有长度为k的区间里找出两个不重叠的最大和，输出这两个最大和所对应的开头的位置a和b。

     一开始没有想到用dp来做，于是有了以下的错误思路（读者可以忽略）：声明一个结构体，包括head（保存起始点）、tail（保存结束点）还有sum（保存长度为k的区间的和）。计算出整个序列所有k个小区间的和sum，按sum从大到小排序（隐含的弊端：排序会导致区间与区间之间起始点和结束点的位置很不确定）由于a、b不能相交，所以当找到没有重叠的部分，就找到当前最优解，但不一定是整个题目的最优解。还要比较各个序列的最优解，以便找到整个题目的最优解，但是重叠的判断会有很多种情况（sum的排序导致的），于是参考了别人的代码......

     正确的思路：当然就是用dp做啦。而且，也是需要计算出所有长度为k的区间的和，按顺序保存在数组b[]中（比我的方法好多啦）。接下来是找出状态转移方程：  max{b[i]} + b[i+k]。另外，考虑到数据比较大，所以用长整型(_int 64）来保存数据。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

#define LL __int64
const int maxn = 200000 + 10;
LL a[maxn], b[maxn];

int main()
{
    int i, j, n, k;
    LL tl, maxt, maxl, maxr, ans;
    while (scanf("%d%d", &n, &k) != EOF)
    {
        LL temp = 0;
        for (i = 1; i <= n; i++)
        {
            scanf("%I64d", &temp);
            a[i] = a[i-1] + temp;       // a[i]保存的是从第1至第i个元素的总和 
        //  printf("a[%d] = %I64d\t", i, a[i]);
        }
        for (i = 0, j = 1; i <= n-k; i++, j++)
        {
            b[j] = a[i+k] - a[i];  　　// b[j]保存的是所有长度为k的区间的总和
        //  printf("b[%d] = %I64d\t", j, b[j]);
        }
        maxt = ans = b[1];
        tl = maxl = maxr = 1;           // maxl: a   maxr：b
        for (i = 1; i+k <= n-k+1; i++)   // 循环的判别要注意，要保证取值不能越界
        {
            if (b[i] > ans)            // 状态转移方程中的max{b[i]},用ans保存
            {
                ans = b[i];
                tl = i;
        //      printf("ans = %I64d\n", ans);
            }
            if (b[i+k] + ans > maxt)
            {
                maxt= b[i+k] + ans;
                maxl = tl;
                maxr = i+k;
        //      printf("maxt = %I64d\n", maxt);
        //      printf("maxl = %I64d\tmaxr = %I64d\n", maxl, maxr);
            }
        }
        printf("%I64d %I64d\n", maxl, maxr);
    }
    return 0;
}