hdu 1024 Max Sum Plus Plus (求一个序列中选出的m个不相交子段和的最大值）

这题真的好难理解好难实现啊。。。。

本来把状态方程写出来就已经有点困难了。。。

要更新状态更难。。。好难啊！！！

最大和子序列的进化版 , 

题意：要求从一序列中取出若干段 , 使得这几段的和最大 .

设 dp[i][j] 为前 j 个数字分成 i 段的最大和 .

转移方程为 :

dp[i][j]=max(dp[i][j-1],max(dp[i-1][k]))+a[j](i-1<=k<=j-1)

其表达的意义就两个不同的决策 : 前者表示与 j-1 所在的一段合并成一段 , 后者表示以

a[j] 为首开始第 i 段 .

pre[j-1]表示max（dp[i-1][k]） i-1<=k<=j-1

#include<cstdio>
#include<iostream>
#include<cstring>
#define INF 0xffffff

using namespace std;

int now[1000010],pre[1000010];
int a[1000010];

int main()
{
    int m,n,maxx;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        memset(now,0,sizeof(now));
        memset(pre,0,sizeof(pre));
        for(int i=1;i<=m;i++)
        {
            maxx=-INF;
            for(int j=i;j<=n;j++)
            {
                now[j]=max(now[j-1],pre[j-1])+a[j];
                pre[j-1]=maxx;
                if(now[j]>maxx)
                    maxx=now[j];
            }
        }
        printf("%d\n",maxx);
    }
    return 0;
}

hdu 1024 Max Sum Plus Plus (求一个序列中选出的m个不相交子段和的最大值）

原文：http://blog.csdn.net/u012841845/article/details/18657229