【HDU】1024 - Max Sum Plus Plus（dp优化）

点击打开题目

Max Sum Plus Plus

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

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 1, S 2, S 3, S 4 ... 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 1, j 1) + sum(i 2, j 2) + sum(i 3, j 3) + ... + 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 1, S 2, S 3 ... 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.

Author

JGShining（极光炫影）

一道卡了很久的题，从今天开始专门拆dp，所以先拿出来开刀了。

首先用初步的思路，建立一个dp[i][j] 的二维数组，i表示有i个子段，j表示以num[j]为结尾。那么：

dp[ i ][ j ] = max (dp[ i-1 ][ t ] , dp[ i ][ j-1 ]) + num[ j ] 这里要特别注意那是t，范围是：1 <= t <= j-1 ，表示 i-1 个子段时前面数所能构成的最大sum。

如果按这个思路实现的话，我们需要3个for循环，而题目给出的n又非常大，所以我们不能这样直接去算( 就算不考虑时间的问题，dp数组都开不开啊！)

然后我参考了：点击打开链接 的思路。

首先是时间上的优化：

计算dp[ i-1 ][ t ] 的时候是浪费了不少时间，但是追根揭底这一步只是要 i-1 个子段时 1 ~ j-1个数中所能构成的最大和，这个值在我们算dp[ i-1 ] [ j-1 ]的时候其实可以得出来，所以我们再开一个数组（我这里命名为maxx[ j ]，原文章不是），这个数组的含义是 i-1 个子段时，前面的数可以构成的最大和（就是dp[ i-1 ][ t ]）。

然后我们来考虑赋值的问题，maxx [ j ] 应该等于 dp[ i ] [ j ]，但是我们并不能直接赋值，因为计算dp[ i ] [ j+1 ] 的时候，还需要用到maxx [ j ] 原来的值，如果冒然赋值则会覆盖掉原来的值。所以我们先把这个（dp[ i ][ j ]）值存到maxx[ n ]上面，当dp[ i ] [ j + 1 ]的时候才赋值就行啦。

然后是空间上的优化：

因为dp数组的两个维度的数值会很大，这个数组也不能使用，我们观察一下，dp数组在递推的过程中，dp[ i - 1][ t ]这个值我们已经用maxx数组很好的解决了，只剩一个dp[ i ] [ j - 1] 的值我们需要用到，那么我们只需要找一个整形变量 t 存一下这个值就行了。

代码如下：（建议先理解思路再打）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MAX 1000000
int n,m;
int num[MAX+11];
int maxx[MAX+11];		//i-1 个子段的最大值 
int t;		//暂时记录 dp[i][j] 的值 
int main()
{
	while (~scanf ("%d %d",&m,&n))
	{
		for (int i = 1 ; i <= n ; i++)
			scanf ("%d",&num[i]);
		CLR(maxx,0);
		for (int i = 1 ; i <= m ; i++)
		{
			t = 0;
			for (int j = 1 ; j <= i ; j++)		//有i个子段，最少从i+1开始计算 
				t += num[j];
			maxx[n] = t;
			for (int j = i + 1 ; j <= n ; j++)
			{
				t = max (maxx[j-1] + num[j] , t + num[j]);
				maxx[j-1] = maxx[n];
				maxx[n] = max(maxx[n] , t);
			}
		}
		printf ("%d\n",maxx[n]);
	}
	return 0;
}