刚写这题时知道是dp但动态转移方程推不出来，后来上网上搜了题解。
先把问题简化，假如就选一段，这就是个经典的max sum dp。
状态转移方程为dp[i]=dp[i-1]+a[i]>a[i]?:dp[i-1]+a[i]:a[i];
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1003
再说这道题http://acm.hdu.edu.cn/showproblem.php?pid=1024；
题意是求不相交且连续的多个子列和的最大值。由一段找最大然后可以想到开一个二维数组dp[i][j];每个状态可理解为分为i段时第j个元素选入时的最大值，所以要么选第j个数时在上一层的基础上从新将第j个数开为一段，要么在本层的基础上加上第j个数，又应为是要最优，自然就要最大，所以得状态转移方程dp[i][j]=max（dp[i][j-1]+a[j],max(dp[i-1][k])+a[j](i-1<=k<j)）;
由于给的范围很大<=1000000;开2维的数组爆内存，所以是否一维的可以，我一开始想时是开两个数组交替，反正只和本层和上层有关，但太麻烦，要交替赋值，时间耗费大。
没次的更新需要用到上一层的到i-1~j-1为止的最大值，所以可以开个数组记录；方程就变成dp[j]=max(dp[j-1]+a[j],pre[j]+a[j]);
最后找dp[n]~dp[p]的最大就行了，n为要分的段，p为元素总个数。
下面看两段代码：
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<stdlib.h> 6 #include<math.h> 7 using namespace std; 8 typedef long long ll; 9 ll a[1000005]; 10 ll aa[1000005];//dp数组 11 ll b[1000005];//记录i-1~j-1的最大值数组 12 //ll pp[1000005]; 13 int main(void) 14 { 15 ll i,j,k,p,q,l,n,m; 16 while(scanf("%lld",&m)!=EOF) 17 { 18 scanf("%lld",&p); 19 if(m>p)//m不可能超过p 20 { 21 m=p; 22 } 23 for(i=1; i<=p; i++) 24 { 25 scanf("%lld",&a[i]); 26 } 27 28 aa[0]=0; 29 memset(b,0,sizeof(b));//每一次b都要初始化 30 for(i=1; i<=m; i++) 31 { 32 for(j=i; j<=p; j++) 33 { 34 aa[j]=aa[j-1]+a[j]>b[j]+a[j]?aa[j-1]+a[j]:b[j]+a[j]; 35 36 } 37 b[i]=aa[i];//本层循环完后更新b数组每次更新要从第i个数开始因为要分成i+1段就必须从能分成i段时加一个数，而分i段必须要i个数。 38 for(j=i+1; j<=p; j++) 39 { 40 b[j]=aa[j-1]>b[j-1]?aa[j-1]:b[j-1]; 41 } 42 } 43 ll maxx=aa[m]; 44 45 for(i=m; i<=p; i++) 46 { 47 if(maxx<aa[i]) 48 { 49 maxx=aa[i]; 50 } 51 } 52 53 printf("%lld ",maxx); 54 55 } 56 57 return 0; 58 59 }
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<stdlib.h> 6 #include<math.h> 7 using namespace std; 8 typedef long long ll; 9 ll a[1000005]; 10 ll aa[1000005]; 11 ll b[1000005]; 12 //ll pp[1000005]; 13 int main(void) 14 { 15 ll i,j,k,p,q,l,n,m; 16 while(scanf("%lld",&m)!=EOF) 17 { 18 scanf("%lld",&p); 19 if(m>p) 20 { 21 m=p; 22 } 23 for(i=1; i<=p; i++) 24 { 25 scanf("%lld",&a[i]); 26 } 27 28 aa[0]=0; 29 memset(b,0,sizeof(b)); 30 for(i=1; i<=m; i++) 31 { 32 for(j=i; j<=p; j++) 33 { 34 aa[j]=aa[j-1]+a[j]>b[j]+a[j]?aa[j-1]+a[j]:b[j]+a[j]; 35 if(j==i) 36 { 37 b[j]=aa[i]; 38 } 39 else 40 { 41 b[j]=aa[j-1]>b[j-1]?aa[j-1]:b[j-1];//此处优化了一下b的更新直接和aa的更新合并并不要在开一重，提高了代码的效率。 42 //因为当前是更新aa[j]所以b[j]记录的是i-1到j-1的最大更新完aa后再更新b并不影响aa[j+1]的更新b[j+1]还是上一层的更新完才变本层的。 43 } 44 45 } 46 47 } 48 ll maxx=aa[m]; 49 50 for(i=m; i<=p; i++) 51 { 52 if(maxx<aa[i]) 53 { 54 maxx=aa[i]; 55 } 56 } 57 58 printf("%lld ",maxx); 59 60 } 61 62 return 0; 63 64 }