HDU 1024 Max Sum Plus Plus（动态规划）

传送门

题意是给你个数字序列，现在让你把这个序列分成m个连续的子序列，且要求这m个子序列的累加和最大。

思路：这道题的题意可以理解为问在序列为末尾时，把序列分为m个子序列这个状态时的最大累加和，那么可以得出这个状态应该是由上一个状态转移得来：（因为dp[i][j]表示数到第j个字符时，前j个数字序列被分为i组时的最大值）dp【i][j]=max(dp[i-1][j]+num[j],dp[i][j-1]+num[j])这两种状态，第一种转移状态意思是第j个数字合并到上一个分组中构成新的分组，第二个状态是第j个数字自己构成一个分组；

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int inf = 0x3f3f3f3f;
using namespace std;
int da[1000010],dp[1000010],a[1000010];
int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m))
    {
        memset(dp,0,sizeof(dp));
        memset(da,0,sizeof(da));
        for(int i = 1;i <= m; i++)
            scanf("%d",&a[i]);
        int res = 0;
        for(int i = 1;i <= n; i++)
        {
            res = -inf;
            for(int j = i;j <= m; j++)
            {
                dp[j] = max(dp[j-1] + a[j],da[j-1] + a[j]);//用上一层到j前面的最大来转移
                da[j-1] = res;//用完了上一层的，即开始把本层的数据作为下一次的迭代的上一层到b前的最大存好
                res = max(res,dp[j]);//同理，把本层作为下一层的上一层存好，因此在所有的循环都结束后，这就是最大值；
            }
        }
        printf("%d\n",res);
    }
    return 0;
}