hdu 1024 Max Sum Plus Plus

Max Sum Plus Plus

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 40437 Accepted Submission(s): 14558

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

题意：让你求的是从n个数中选取m个部分后所能得到的最大子段和，且m个部分不能有相交的部分（如，sum（2，4）//第二个到第四个+sum（3，5）//第三个到第五个就不行）。

思路：这题的数据特别大，用暴力显然是不行的，所以我们得想别的方法。

首先，我们可以先看暴力做法的大致思路：首先，我们应该是遍历每一种将n个数选取m段连续子段然后求出他们的最大和，再从这些数里找出最大的那个就是答案，从这个思路中我们可以得到要求出答案就要先将n个数中选取m段。

接下来说句特重要的话：要得出问题的最优解，我们可以把问题分成许多有联系的子问题，再将所有子问题的最优解求出最终就能得到我们要的问题的解。

知道这个之后我们就能把题目中从n个数中选取m段求出最大和分解成从n个数中选取（1段，2段，3段...........m段）的最大和。

那我们先从1段开始分析：n个数选取1段求最大的和是多少，我们从第一个数开始选，这时的问题就是从一个数中选一段的最大和，显然就是这个数的值，然后我们在看第二个数，这时我们就要考虑这两种情况（1：不选这个数和更大。2：选这个数和更大（这种情况不能仅仅用之前选出的最大值+这个数，看第三个数你就知道了）），我们从这两种情况种得出最大的值就是从两个数中选取1段的最优解，我们在看第三个数，他也要考虑要不要选他，我们用一个例子来说明（假设，我们是1，-2，3这三个数，我们在第一第二步得出的最大和都是1，当到第三个数时，我们因去遍历前面的每一个与3有关的连续字段得出最大值（显然这个值是只选第三个），而不是用前面2个数求出的值+3了。这时我们的出了3，他和前面1相比取大就好了），后面的以此类推，一直到第n个数，我们就把把n个数分成1段对于每个数的所有最优解求出来了，为什么我们要这样求呢？我们看分成2段时的求法。

选取两段：两段时，我们应该从第二个数开始，因为两个数才能分成两段，第二个数时的最大和也就是他们两的和，那我们再看第三个数时，我们也是考虑要不要把它加到分两段的情况里，那我们也有那两种情况（选与不选），选的话我们就要从头遍历前面分成2段时与这个数有关的所有情况，显然这时不行的，那我们应该怎么做呢，其实想想上面那句特重要的话就可以知道了，我们将选取两段分成先选取一段，求出一段的最优解，再在分两段时从这个数前面分一段的最优解中选取最大值加上这个数和不选这个数取最大就行了。

。。。。。。

选取n段：向上面一样，我们就可以从n-1段中得到答案；

看样例二的求解过程图把：

显然，最后输出8就好。

其实这就是dp；

接下来看动态转移方程：我们可以从上面的分析得出方程为dp[i][j]=max(dp[i][j-1],max(dp[i-1][k](i<=k<j)+a[j]))(1<=i<=m;i<=j<=n)

我们来看这个求解过程的时间复杂度，

实现过程

for(i=1~m)

　　for(j=i~n)

　　　　for(k=i~j)

这时三个for嵌套，前两个for在最差的情况复杂度就是O（n！），如果我们加上第三个就是O（n！*一个值），这个值显然不小（不好意思，不会算），所以这是没法用它来求解这题的。

我们再看空间复杂度，它应该是1e6*1e6，显然他也不行。

那我们就要想办法优化他们两。

dp[i][j]=max(dp[i][j-1],max(dp[i-1][k](i<=k<j)+a[j]))(1<=i<=m;i<=j<=n)

空间的话我们可以发现我们得出第i段答案时只需i-1的答案，所以可以不要这一维，或者把这一维大小设为2，滚动（0，1）来存。

时间的话我们可以发现我们要的是i-1中（i<=k<j）中的最大值，那我们可以在一开始i==j时就开始记录最大值，用一个变量一直更新它，这样就不用第三个for了。

代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 #define LL long long
 5 #define mem(a,b) memset(a,b,sizeof(a))
 6 using namespace std;
 7 LL dp[2][1000010];//dp[i][j]=k是i是分i段，j是前j个数，k是前j个数分i段的最大值 
 8 //dp[i][j]=max(dp[i][j-1]//不选第j个数,max（dp[i-1][k]/i-1<=k<j，dp[i][j-1])+第j个数//选第j个数） ,答案是dp[m%2][n];
 9 //可优化：即 1：dp[i-1][k]/i-1<=k<j，可用一个变量记录它
10 //            2： 只有dp[i][j-1]和dp[i-1][j-1]用得到，所以只需一维开2这么大就行 
11 int num[1000010];
12 LL up_max;
13 int main(){
14     int m,n;
15     int k;
16     while(~scanf("%d%d",&m,&n)){
17         mem(dp,0);
18         mem(num,0);
19         up_max=0;
20         for(int i=1;i<=n;i++){
21             scanf("%d",&k);
22             num[i]+=num[i-1]+k;
23         }
24         int t=0;
25         for(int i=1;i<=m;i++){
26             for(int j=i;j<=n;j++){
27                 if(i==j){
28                     up_max=dp[t][j]=num[j];//**！！！！*给dp赋初值，如果不写，则dp的第一个可能会是重j-1个数中选出i种，但是i==j只有从j个数中才可选出i种 
29                     //up_max是每一个重j-1分i段的最大和，所以也要赋初值 
30                 }else{
31                     up_max=max(up_max,dp[1-t][j-1])+num[j]-num[j-1];
32                     dp[t][j]=max(dp[t][j-1],up_max);
33                 }
34             }
35             t=1-t; //让数组一维滚动交换为（0，1）
36         }
37         t=1-t;//最后多减了一次，再减一下
38         cout<<dp[t][n]<<endl;
39     }
40     return 0; 
41 }

2019-03-04

21:08:22