关键词：
这道题弄了很久，网上的很多都看不懂，所以想要写一个像我这种菜鸟都可以看得懂的解析。
题意是将一个长度为n的序列，分成m段不相交叉的子段，使得他们的和最大。
于是可以用dp[i][j]来表示在前j个数中，以num[j]结尾并分为i段的最大和。此时我们可以得出一个式子，dp[i][j]=max(dp[i-1][k]+a[j],dp[i][j-1]+a[j]) (i-1< k< j-1)。分别表示num[j]单独成段和num[j]加入以num[j-1]结尾的一段。
现在举一个例子，序列为-1,4,-2,3,-2,3。
现在可以结合图标来理解式子的意思了，例如dp[2][4]=max(max(-1,4,2,) , 2)+num[4]=7
也就是说计算dp[i][j]只用到了2层的数据，上一层的数据我们只用到了其中的最大值，于是在求dp[j]时，我们可以用premax[]来记录i～j的最大值，在下一层时使用。
为什么i=n时，从第n位开始有值呢？因为这是每个数字自己单独成一段的情况，是满足分成n段的必要条件。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1000000;
int num[maxn],premax[maxn],dp[maxn];
int main()
int n,m,temp;
while(~scanf("%d %d",&m,&n))
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
memset(dp,0,sizeof(dp));
memset(premax,0,sizeof(premax));
for(int i=1;i<=m;i++)
temp=-1e9;
for(int j=i;j<=n;j++)
dp[j]=max(premax[j-1],dp[j-1])+num[j];
premax[j-1]=temp;//temp存放的是i～j-1中的最大值
temp=max(temp,dp[j]);
printf("%d\n",temp);
return 0;
hdu1024maxsumplusplus(dp)
hdu1024MaxSumPlusPlusNowIthinkyouhavegotanACinIgnatius.L‘s"MaxSum"problem.TobeabraveACMer,wealwayschallengeourselvestomoredifficultproblems.Nowyouarefacedwithamoredifficultproblem. Givenaco 查看详情
hdu-1024maxsumplusplus
MaxSumPlusPlusTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):30478 AcceptedSubmission(s):10750ProblemDescripti 查看详情
[2016-03-28][hdu][1024][maxsumplusplus]
时间:2016-03-2817:45:33星期一题目编号:[2016-03-28][HDU][1024][MaxSumPlusPlus]题目大意:从n个数字提取出一定数字组成m个部分,使得这个部分的总和最大分析:dp[i][j]表示前i段计算第j个数字,dp[i][j]=max(dp[i-1][j-1]+a[j],dp[i][k]+a[j]);#include<algorithm&g... 查看详情
hdu1024maxsumplusplus
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1024http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1053【题解】本题也是51nod1053最大m子段和和上题很像如果正数个数<段数，那么输出前m大。否则考虑线段树，跟bzoj3638一个做法。如果中... 查看详情
hdu1024maxsumplusplus——dp+滚动数组
题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=1024 MaxSumPlusPlusTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):31798&nbs 查看详情
hdu1024maxsumplusplus(子段和最大问题)
MaxSumPlusPlusTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):17336 AcceptedSubmission(s):5701ProblemDescriptio 查看详情
hdu1024maxsumplusplus（基础dp)(代码片段)
MaxSumPlusPlusTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):34541 AcceptedSubmission(s):12341ProblemDescripti 查看详情
hdu1024maxsumplusplus动态规划
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1024题目大意：n个数分成两两不相交的m段，求使这m段和的最大值。解题思路：比较坑的点：n2 能过；longlong超时，intAC。 dp[i][j]:=在选择第i个数的情况下前i个数分成j段的最大值d... 查看详情
hdu1024maxsumplusplus（dp）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1024题目大意：有多组输入，每组一行整数，开头两个数字m,n，接着有n个数字。要求在这n个数字上，m块数字的最大和。比如26-14-23-23，就是（4-23）和（3）这两块最大和为8。解题思路：... 查看详情
maxsumplusplus(动态规划)hdu1024(代码片段)
题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=1024(http://www.fjutacm.com/Problem.jsp?pid=1375)题意：长度为n的序列里，m段不相关区间的最大和思路：我们先要确定一个东西，就是状态，这里我用dp[i][j]表示前j个数在取a[j]情况下分i段的最大... 查看详情
hdu1024maxsumplusplus（简单dp）
题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1024题意：给定一个数组，求其分成m个不相交子段和的最大值。这题有点问题其实m挺小的但题目并没有给出。dp[i][j]表示取第i位的数共取了j段然后转移方程显然为dp[i][j]=max(dp[i-1][j]+a[... 查看详情
hdu1024maxsumplusplus
思考：（这道题是抄kuangbin聚聚的），这个题给了2种状态，一个是段数，一个是数值，我感觉关于dp来说，最难定义的就是状态（可能我还没有入门）感觉定义了好的状态，在推到状态转移方程的时候才会更容易推出（虎爷说过... 查看详情
hdu1024maxsumplusplus
题意：最大子序列和加强版，恰好有m个子序列，输出这m个子序列的最大和分析:先想一下最大子序列和，用dp[i]表示选第i个数的最大和，那么max(dp[i])0<i<=n就是答案恰好分为m个，那么增加一维表示选第i个并且恰好分为j块的... 查看详情
hdu-1024maxsumplusplus(dp+滚动数组优化)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1024题意：给定n个数字，求其中m段的最大值（段与段之间不用连续，但是一段中要连续）例如：251-223-1五个数字中选2个，选择1和23这两段。 题解：dp[i][j]从前j个数字中选择i段，然... 查看详情
hdu1024maxsumplusplus（m个子段的最大子段和）(代码片段)
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1024MaxSumPlusPlusTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):35988 查看详情
hdu-1024maxsumplusplus滚动数组优化
给定n个数字，求其中m段的最大值（段与段之间不用连续，但是一段中要连续）例如：25 1-223-1五个数字中选2个，选择1和23这两段。dp[i][j]从前j个数字中选择i段，然后根据第j个数字是否独立成一段，可以写出状态转移方程:dp[... 查看详情
hdu1024maxsumplusplus(代码片段)
MaxSumPlusPlusTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):40437 AcceptedSubmission(s):14558ProblemDescriptionNowIthinkyouhavegotanACinIgnatius.L‘s"MaxSum"problem.TobeabraveACMer,wealwayschallengeourselvest... 查看详情
hdu-1024maxsumplusplus（最大m段子序列和-dp）(代码片段)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1024题目大意：给m和n个数,将n个数分为m段,不交叉,求m段和的最大值。SampleInput1312326-14-23-23SampleOutput68emmm，先想容易的，我们应该很容易想到设置状态$dp[i][j]$表示在第$j$个字段末尾分为$i... 查看详情