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

转载于:https://www.cnblogs.com/SYCstudio/p/7419305.html

相关资源：JAVA上百实例源码以及开源项目