这题真的好难理解好难实现啊。。。。
本来把状态方程写出来就已经有点困难了。。。
要更新状态更难。。。好难啊！！！
最大和子序列的进化版 ,
题意：要求从一序列中取出若干段 , 使得这几段的和最大 .
设 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;
}