Max Sum Plus Plus

*Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 47562 Accepted Submission(s): 17318
*

Problem Description

Now I think you have got an AC in Ignatius.L's "Max Sum" problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.

Given a consecutive number sequence S1, S2, S3, S4 ... Sx, ... Sn (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ Sx ≤ 32767). We define a function sum(i, j) = Si + ... + Sj (1 ≤ i ≤ j ≤ n).

Now given an integer m (m > 0), your task is to find m pairs of i and j which make sum(i1, j1) + sum(i2, j2) + sum(i3, j3) + ... + sum(im, jm) maximal (ix ≤ iy ≤ jx or ix ≤ jy ≤ jx is not allowed).

But I`m lazy, I don't want to write a special-judge module, so you don't have to output m pairs of i and j, just output the maximal summation of sum(ix, jx)(1 ≤ x ≤ m) instead. ^_

Input

Each test case will begin with two integers m and n, followed by n integers S1, S2, S3 ... Sn.
Process to the end of file.

Output

Output the maximal summation described above in one line.

Sample Input

1 3 1 2 3
2 6 -1 4 -2 3 -2 3

Sample Output

6
8

Hint
Huge input, scanf and dynamic programming is recommended.
 

给定一个序列,求最大M字段和;

双动态规划:

假设命令为"前 项分成 段所得到的最大值";

那么,其实这个样子是不好进行状态转移的,你看当前这一步如果是考虑"第 个元素选还是不选"的话,显然当不选的时候状态可以由转移过来,但是要选上第 个元素的时候,就不好转移了.

在这种"不好转移"的情况下,可以考虑添加描述状态的参数的个数/增加限制条件,重新设计状态

记 为前 个元素分成 段,且第 个元素一定被选上的状态......既然第 个元素肯定被选上了,我就可以考虑:这个元素到底是单独一个段呢,还是和它前面的元素一个段呢?后一种情况显然是就可以解决的,但是第一种情况,其实就是"前 个元素的最大 子段和问题",可以枚举从 到 的所有情况,即

然后就要考虑优化了,因为这样显然是不优的......

可否把这个值提前求出来,然后找个地方保存起来呢?

好像是可以的,因为我求 的时候可以顺手把最大值保存下来呢.

假设 表示了前 个元素最大 子段和的答案,那么显然根据最后一个元素拿还是不拿得到:

如果对应的 不存在的话,可以考虑设置成 ;

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int MAX_N = 1e6 + 7;
const int INF = 1e9 + 7;
int a[MAX_N], dp[MAX_N][MAX_N], ans[MAX_N][MAX_N];

int M, N;

int main(){
    ios::sync_with_stdio(0);
    while(cin>>M>>N){
        for (int i = 1; i <= N; i++){
            cin >> a[i];
        }
        memset(dp, 0, sizeof dp);
        memset(ans, 0, sizeof ans);
        for (int i = 1; i <= M; i++){
            ans[(i + 1) % 2][i - 1] = -INF;
            for (int j = i; j <= N; j++){
                dp[i][j] = max(dp[i][j - 1], ans[i][j]) + a[j];
                ans[i + 1][j + 1] = max(ans[i + 1][j], dp[i][j]);
            }
        }
        cout << ans[M + 1][N + 1] << endl;
    }
    return 0;
}

但是这个数组显然连编译都没法通过啊......因为二维数组实在是太大了......于是还要用滚动数组优化一下;

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int MAX_N = 1e6 + 7;
const int INF = 1e9 + 7;
int a[MAX_N], dp[MAX_N], ans[3][MAX_N];

int M, N;


int main(){
    ios::sync_with_stdio(0);
    while(cin>>M>>N){
        for (int i = 1; i <= N; i++){
            cin >> a[i];
        }
        memset(dp,0,sizeof dp);
        memset(ans, 0, sizeof ans);
        for (int i = 1; i <= M; i++){
            ans[(i + 1) % 2][i - 1] = -INF;
            for (int j = i; j <= N; j++){
                dp[j] = max(dp[j - 1], ans[i % 2][j - 1]) + a[j]; 
                ans[(i + 1) % 2][j] = max(ans[(i + 1) % 2][j - 1], dp[j]);
            }
        }
        cout << ans[(M + 1) % 2][N] << endl;
    }
    return 0;
}

注意一点啊,就是ans第一个值要初始化成 ,因为序列里面可能有负数,如果放着不管(就是)的话,有可能影响最后的结果.