题面

数列求和2
Time Limit: 1000MS Memory limit: 65536K

题目描述
给出一个数列 S 1, S 2, S 3, S 4 ... S x, ... S n (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S x ≤ 32767). 我们定义 sum(i, j) = S i +S i+1+ ... + S j (1 ≤ i ≤ j ≤ n).
现在给你一个整数 m (n>=m > 0), 你的任务是找出m对 i，j 使 sum(i 1, j 1) + sum(i 2, j 2) + sum(i 3, j 3) + ... + sum(i m, j m) 最大化 (i x ≤ i y ≤ j x 或 i x ≤ j y ≤ j x 是不允许的).
结果仅输出sum(i x, j x)的最大累加和(1 ≤ x ≤ m) 就行了.

输入
包含多组数据，每组数据占一行，前两个整数是m和n，后面紧跟着是n个整数S 1, S 2, S 3 ... S n.

输出
输出所描述的结果，每一组的结果占一行

示例输入
1 3 1 2 3
2 6 -1 4 -2 3 -2 3

示例输出
6
8

提示

来源
“师创杯”山东理工大学第八届ACM程序设计竞赛

解题思路

对本蒟蒻来说难度不小的 DP，推出状态转移方程后还需要使用滚动数组优化一下。具体题解请参考学长的博客：http://blog.csdn.net/u013569304/article/details/51321705 或自行搜索 「HDOJ 1024: Max Sum Plus Plus」 的相关题解。

参考代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int a[1000001];
long long dp[1000001], maxn[1000001];

int main(int argc, char const *argv[]) {
    int m, n;
    while(~ scanf("%d %d", &m, &n)) {
        for(int i=1; i<=n; ++i) {
            scanf("%d", &a[i]);
            dp[i] = -1e15;
            maxn[i] = -1e15;
        }
        long long ans = -32768;
        dp[0] = maxn[0] = 0;
        for(int i=1; i<=n; ++i) {
            for(int j=1; j<=i; ++j) {
                dp[j] = max(dp[j]+a[i], maxn[j-1]+a[i]);
                maxn[j-1] = max(maxn[j-1], dp[j-1]);
                if(j==m || j==i)
                    maxn[j] = max(maxn[j], dp[j]);
                if(j == m)
                    ans = max(ans, dp[j]);
            }
        }
        printf("%lld\n", ans);
    }
    
    return 0;
}