Max Sum Plus Plus_牛客博客

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 S ₁, S ₂, S ₃, S ₄ ... S _x, ... S _n (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S _x ≤ 32767). We define a function sum(i, j) = S _i + ... + S _j (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(i ₁, j ₁) + sum(i ₂, j ₂) + sum(i ₃, j ₃) + ... + sum(i _m, j _m) maximal (i _x ≤ i _y ≤ j _x or i _x ≤ j _y ≤ j _x 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(i _x, j _x)(1 ≤ x ≤ m) instead. ^_^

Input Each test case will begin with two integers m and n, followed by n integers S ₁, S ₂, S ₃ ... S _n.
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，n分别表示成m组，一共有n个数即将n个数分成m组，m组的和加起来得到最大值并输出。

请注意本题的数据比较大，用二维数组会爆炸emmm。

状态转移方程：dp[j] = max(dp[j-1]+s[j],pre[j-1]+s[j]);

其中dp[j]代表当前状态这个圈内的最大数，s[j]是输入的要计算的数组，

dp[j-1]+s[j]代表还是这个圈加上当前s[j]这个数，

pre[j-1]+s[j]代表新开一个圈。

重点就是s[j]到底放在前一个圈，还是新的圈中。还要压缩二维变为一维，就需要加个pre[]数组。

如果数据不是很大，可以开二维：

动态转移方程：dp[i][j]=max(dp[i][j-1]+a[j],max(dp[i-1][k])+a[j]) (0<k<j)

dp[i][j-1]+a[j]表示的是前j-1分成i组，第j个必须放在前一组里面。

max( dp[i-1][k] ) + a[j] )表示的前（0<k<j）分成i-1组，第j个单独分成一组。

但是题目的数据量比较到，时间复杂度为n^3，n<=1000000，显然会超时

上代码，本题用的一维dp

#include <iostream>
#include <string>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <set>
#include <sstream>
#include <map>
#include <cctype>

using namespace std;
#define Start clock_t start = clock();
#define End clock_t end = clock();
#define Print cout<<(double)(end-start)/CLOCKS_PER_SEC*1000<<"ºÁÃë"<<endl;
const int inf = 99999999;
const int maxn = 1000000 + 5;
int s[maxn];
int dp[maxn];
int pre[maxn];
int main()
{
    int m,n,maxi;
    while(cin>>m>>n){
        for(int i = 1;i <= n;i++) cin>>s[i];
        memset(dp,0,sizeof(dp));
        memset(pre,0,sizeof(pre));
        for(int i = 1;i <= m;i++){
            maxi = -inf;
            for(int j = i;j <= n;j++){
                dp[j] = max(dp[j-1]+s[j],pre[j-1]+s[j]);
                pre[j-1] = maxi;
                maxi = max(maxi,dp[j]);
            }
        }
        cout<<maxi<<endl;
    }
    return 0;
}