HDU-1024-Max Sum Plus Plus(DP)
Max Sum Plus Plus
题意：
给出一列n个整数，然后要把他们分成m段，使得m段的和最大。
分析：
把n个整数分成m段，还要让这m段的和最大
d[i][j]表示前 i 个数在做选取第 i 个数的前提下，分成 j 段的最大值。（1<=j<=i<=n&&j<=m)
d[i][j] = max(d[i-1][j]+a[i],max(d[j-1][j-1]~d[i-1][j-1])+a[i])
第一备选项是d[i-1][j]+a[i],很容易理解，但是第二备选项，是要先求出分成 j-1段的最大值，然后再加上当前的a[i]，这意味着是从j-1段增加一段到j段。所以我们只要把这个最大值，都保存下来就可以了。
由于数目比较多，采用滚动数组的方法，但是如何求每分段的最大值呢？
我们需要一个同样大的数组c，对于c[i-1][j-1],保存max(d[j-1][j-1]~d[i-1][j-1])。每一次决策d[i][j]之后，更新 c [i][j]。
转换成滚动数组之后，动态转移方程变成
d[i] = max(d[i-1]+a[i],c[i-1]+a[i])
但是需要注意，现在是在处理第 j 段的情况，但是我们用的 c 数组是保存着 j-1 段的情况，所以我们必须迟一步更新c数组，否则会影响到d数组的更新。先用 j-1 段的 c[i-1] 更新 d[i] ，然后利用储存 着 j 段max(d[1]~d[i-1])的 t 更新 j 段c[i-1],然后当更新完 c[i-1]之后，利用t = max(t,d[i])保存当前最大值，以便利于 j+1 段中d[i+1]的更新。
#define MAX 1000010
int a[MAX],d[Max],c[Max];
int main()
{
int m,n;
while(cin>>m>>n)
{
d[0] = 0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
memset(c,0,sizeof c);
memset(d,0,sizeof d);
int t=0;
for(int j=1;j<=m;j++)
{
t = -inf;//初始化每一阶段的最大值为t.
for(int i=j;i<=n;i++)
{
d[i] = max(d[i-1]+a[i],c[i-1]+a[i]);//每一次决策
c[i-1] = t;//更新当前段的最大值
t = max(t,d[i]);//更新当前的段的最大值。
}
}
cout<<t<<endl;
}
return 0;
}