HDU-1024Max Sum Plus Plus（最大m段子序列和-DP）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1024

题目大意：给m 和n个数,将n个数分为m段,不交叉,求m段和的最大值。

Sample Input

1 3 1 2 3
2 6 -1 4 -2 3 -2 3

Sample Output

6
8

emmm，先想容易的，我们应该很容易想到设置状态$dp[i][j]$表示在第$j$个字段末尾分为$i$段的最大值，那么则有$dp[i][j]=max(dp[i][j-1]+a[j],pre[i-1][j-1]+a[j])$也就是该数字要么和之前的数字连接起来也就是$dp[i][j-1]+a[j]$，要么自成一段，就是$pre[i-1][j-1]+a[j]$，其中$pre[i][j]$表示在$j$之前分为$i$段的最大值是多少。

那么我们看到，实际上用到的只有上一段，也就是说我们完全可以直接将其化为滚动数组。那么代码也就出来了

以下是AC代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long ll;
const int mac=1e6+10;
const ll inf=1e15+10;

int a[mac];
ll dp[mac],pre[mac];

int main(int argc, char const *argv[])
{
    int m,n;
    while (~scanf ("%d%d",&m,&n)){
        for (int i=1; i<=n; i++)
            scanf ("%d",&a[i]);
        memset(dp,0,sizeof dp);
        memset(pre,0,sizeof pre);
        dp[0]=-inf;
        ll mi;
        for (int i=1; i<=m; i++){
            mi=-inf;
            for (int j=i; j<=n; j++){
                dp[j]=max(dp[j-1]+a[j],pre[j-1]+a[j]);
                pre[j-1]=mi;
                mi=max(mi,dp[j]);
            }
        }
        printf("%lld
",mi);
    }
    return 0;
}