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 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. ^_^

输入

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 the maximal summation described above in one line.

输入示例

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

输出示例

6
8

Hint

Huge input, scanf and dynamic programming is recommended.

题目大意：

给定n个数，让其划分为k个不重叠的区间（不要求连续），求其中的最大值。

思路：

因为给定一个区间，它的最大值是确定的，所以具有无后效性，所以我们考虑使用dp来解此题。

我们首先定义状态表示，很自然的想到：

1
dp[i][j] = dp[i][j] 表示将前i个数字分成j段的最大子段和。

接下来考虑状态转移方程：

我们将状态转移分为：

  • 与前面划分的区间不合并，即自成一组。
  • 与前面划分的区间合并为一组。

第二种转移方程比较好考虑：

1
dp[i][j] = dp[i-1][j] + v[i];

自成一组需要找上一组从哪里转移。由于不需要保证连续性，所以就需要从第一段一直到j-1段都要考虑到。

1
dp[i][j] = max{dp[k][j-1](1 <= k < i)}

由于只有k个长度的字符才能分成k段。所以这里取值范围应该改为:

1
dp[i][j] = max{dp[k][j-1](j-1 <= k < i)} + v[i]

综合一下就是：

1
dp[i][j] =max( dp[i-1][j], max{dp[k][j-1](j-1 <= k < i)} ) + v[i]

分析工作准备完毕，我们准备写代码时发现，这个数组范围比较大，会O（n2）的算法会超时，所以要优化。

第二种转移方程没什么好优化的，我们转移到第一种上，它在转移上依赖了他之上的好多行的数组，列却只依赖一列。这里想象为二维数组，我们把行，列的含义互换，想象这个二维数组逆时针旋转了90度。
就得到了如下的转移方程：

1
dp[i][j] = dp[i][j] 表示将前j个数字分成i段的最大子段和。
1
dp[i][j] =max( dp[i][j-1], max{dp[i-1][k](i-1 <= k < j)} ) + v[j]

我们可以将 max{dp[i-1]k} 这个O(n)的时间，在上一层的d[i-1][j]计算结果时用一个变量来记录，使其优化为O(1)。

具体编程还是有些难度，需要好好思考。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
 * @Date: 2020-01-24 10:42:12
 * @LastEditors  : BeckoninGshy
 * @LastEditTime : 2020-01-25 11:37:00
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN =1e6+10;
int dp[MAXN],v[MAXN],numax[MAXN]; //保存上一层dp的最大值。

int main(){
    int k,n;
    while(cin >> k >> n){
        for(int i = 1; i <= n; i++){
            cin >> v[i];
            dp[i] = numax[i] = 0;
        }
        dp[0] = numax[0] = 0;
        int lastmax = INT_MIN;
        for(int i = 1; i <= k; i++){
            lastmax = INT_MIN; //保存上一层dp的最大值
            for(int j = i; j <= n; j++){
            	//先利用之前的上一层最大值更新当前状态， 
                dp[j] = max(dp[j-1],numax[j-1]) + v[j];
                //再将j-1的最大值更新到上一层的最大值数组中， 将在i+1层循环中使用，当前循环不使用
                numax[j-1] = lastmax;
                //存储当前层的最大值 
                lastmax = max(lastmax,dp[j]); 
            }
        }
        cout << lastmax << endl;
    }
    return 0;
}