题目链接 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[j] , max(dp[j - 1][j - 1]~dp[i - 1][j - 1]))（大致意思是取第i位要么i-1位取了j个那么a[j]刚好能与i-1拼成一段，或者j - 1

到i - 1中取j - 1段的和的最大值与a[j]组成j段）

但是m题目没有给出，所以直接设dp[i]外面再套层循环1～m。至于怎么求原来dp中的max(dp[j - 1][j - 1]~dp[i - 1][j - 1])，可以用maxsum[j - 1]表示

然后maxsum[j - 1]的值就是上一组dp[j - 1]的值。

#include <iostream>#include <cstring>#include <cstdio>#define inf 0X3f3f3f3fusing namespace std;const int M = 1e6 + 10;int maxsum[M] , dp[M] , a[M];int main(){    int n , m , MAX;    while(scanf("%d%d" , &m , &n) != EOF) {        for(int i = 1 ; i <= n ; i++) {            scanf("%d" , &a[i]);            dp[i] = 0;            maxsum[i] = 0;        }        for(int i = 1 ; i <= m ; i++) {            MAX = -inf;            for(int j = i ; j <= n ; j++) {                dp[j] = max(dp[j - 1] + a[j] , maxsum[j - 1] + a[j]);                maxsum[j - 1] = MAX;                MAX = max(MAX , dp[j]);            }        }        printf("%d\n" , MAX);    }    return 0;}

hdu 1024 Max Sum Plus Plus（简单dp）