HDU 1024 Max Sum Plus Plus (动态规划)

时间:2021-09-06 20:02:31

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;
}