HDU Max Sum Plus Plus

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 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_xor i_x≤ j_y≤ j_xis 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

题意分析：

就是给你一个连续的序列，叫你求出如何进行划分，是区间可以刚好是M个区间的前提下是的这M个区间的和最大。

思路分析：

处一看题，以为是一道二分枚举，后来发现是自己脑残了。其实本质是一个经典的动态规划。即，DP问题。

算法分析：

既然，我都说了是DP了那么我么就直接切入主题吧。是DP当然有状态转移方程式。我们知道动态规划的核心思想是最优子结构，也就是说当我们遇到一个问题的时候，我们都有两种选择。即使，你要么选择该状态，要么你不选择。但前提是你必须保证最后会得到最优子结构。

Ok，下面说一下这道题的思路吧。跟据上面所说的我们可以得出下面的状态转移方程式：

b(i,j) = MAX{b(i,j-1)+num[i], MAX{b(i-1,t)}+num[i]};（0<=i<=j<=n，t<j）

其中的i，j表示前i段的前j项。而约束条件很显然。

然后，我想解释一下这个转移方程式，是什么意思呢？即，在第i段的时候，你对前j项有两种选择。第一，要么你

将该项加入到前面的j-1项当中；第二，要么你可以将该项不与前面的j-1项组成一段，即第j项单独开辟一段。然后，就是动态规划的核心思想了，即，求最优子结构，选两种选择中的最优的一种。

则，该算法的时间是O（m*n*n）空间是m*n。对平时玩玩倒是可以，但是对于竞赛来说那是No Way。那难道是无解吗？当然不是。不知道你是否还记得那个神奇的滚动数组。下面我们之所以可以优化就是因为他。

优化版：

我们可以从上面的动态转移方程式中发现，当求b(i,j)的时候，其实他是只跟b(i,j-1) 和 b(i-1,t)有关的。所以，我们可以压缩i维，使其变成一维数组。从而时间也变成了O(M*N)，空间为N。而此时我们的问题有来了，我们该如何求得压缩后的值呢？其实，很显然的我们此时要开两个数组来保存b(i,j-1)和b(i,t)。而你是否对时间为何降到O（M*N）而感到疑惑呢？其实，这里时间之所以会降是因为之前的算法中存在着一个Max{b(i-1,t)}这个数组的遍历。但其实这个遍历是可以省略的，因为在前面阶段我们就可以求出了MAX{b(i-1,t)}。所以此时我们可以继续用一个数组保存Max{b(i-1,t)}。但是我们都知道搞竞赛的题目一般都很扣的，他会要求你一省在省。所以此时我们注意到了原先保存b(i-1,t)的数组只在Max{b(i,j-1)+num[j],MAX{b(i-1,t)}+num[j]}中使用一次，而我们为什么不资源回收利用呢？答案是显然的。

所以，总上所述我么可以慢慢的推出了一个时间复杂度是O（N*M）空间是线性的算法。

下面是状态转移方程式：

dp[j] = MAX(dp[j-1],t[j-1]) + num[j]

更多的内容自己看下面的代码吧！

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

const int INF = 0x7fffffff;  //征战这么久了，居然被这个给坑了两个小时!!!
const int N = 1E6 + 5;
int dp[N],t[N],num[N];
int main()
{
    int n,m,i,j;
    while(cin>>m>>n)
    {
        for(i = 1;i <= n;++i){
           cin>>num[i];
           dp[i] = 0;
           t[i] = 0;
        }
        dp[0] = 0,t[0] = 0;
        int sum = 0;
        for(i = 1;i <= m;++i){
          sum = -INF;
          for(j = i;j <= n;++j){
            dp[j] = max(dp[j-1],t[j-1]) + num[j];  //保存着i-1阶段的maxsum
            t[j-1] = sum;                          //保存着i+1阶段的maxsum
            sum = max(dp[j],sum);
          }
          t[j-1] = sum;
        }
        cout<<sum<<endl;
    }
}