HDU 1024 Max Sum Plus Plus （动态规划）

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

Http

HDU:https://vjudge.net/problem/HDU-1024

Source

动态规划

题目大意

给出一个数列，求m段不相交的子区间使得区间和最大

解决思路

首先可以很快列出简单的动态转移方程，设Arr[i]表示原来数列中第i个数，设F[i][j]表示前j个数中选出i个区间的最大和。因为第i个数可以新开一组，也可以加入原来的一组中，所以有转移方程

\(F[i][j]=max(F[i][j-1]+Arr[j],max(F[i-1][(i-1)……(j-1)])+Arr[j])\)

(感谢@宫园薰指正方程中出现的错误)

因为题目中没有给出m的范围，而F[i]又只与F[i]前面的以及F[i-1]有关系，所以我们可滚动的做。

但这样还是会超时的，我们发现，转移的瓶颈在max(F[i][0……(j-1)])这里，即前面的最大值。而这是可以在推导F的时候一并记录下来的。所以我们可以设Pre_max[i]表示前i个中的最大值。那么转移方程就可以写成：

\(F[j]=max(F[j-1]+Arr[i],Pre\_max[j-1]+Arr[j])\)注意i那一维滚动掉了。

要注意信息的更新顺序。

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

const int maxN=1000011;

const int inf=2147483647;

int n,m;

int Arr[maxN];

ll F[maxN];

ll Pre_max[maxN];

int main()

{

	while (cin>>m>>n)

	{

		for (int i=1;i<=n;i++)

			scanf("%d",&Arr[i]);

		memset(F,0,sizeof(F));

		memset(Pre_max,0,sizeof(Pre_max));

		ll nowmax;

		for (int i=1;i<=m;i++)

		{

			nowmax=-inf;//记录当前的max，方便更新Pre_max

			for (int j=i;j<=n;j++)//注意这个循环中三个信息更新的先后顺序，另外这个j从i开始，因为要分出i组一定要至少有i个数

			{

				F[j]=max(F[j-1]+Arr[j],Pre_max[j-1]+Arr[j]);//新开一组，或加入到之前的最大的一组中去

				Pre_max[j-1]=nowmax;//更新前面最大的

				nowmax=max(nowmax,F[j]);//更新当前最大的

			}

		}

		printf("%lld\n",nowmax);

	}

	return 0;

}