题目:http://acm.hdu.edu.cn/showproblem.php?pid=1024
转移方程是dp[i][j]=max{dp[i][j-1]+a[j],dp[i-1][k]+a[j]} (i = 1-->n) (j = i-->n) (k =i-1-->j-1)
别人的代码:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#define N 1000001
using namespace std;
int m,n,Max; //Max保存这最大值
int now[N]; //包含第j个数据的最大和
int pre[N]; //前j个数据的最大和
int a[N];
int main()
{
//freopen("in.txt","r",stdin);
int i,j;
while(scanf("%d%d",&m,&n)==2)
{
for(i=1;i<=n;i++) scanf("%d",&a[i]);
memset(now,0,sizeof(now));
memset(pre,0,sizeof(pre));
for(i=1;i<=m;i++)
{
Max=-99999999;
for(j=i;j<=n;j++)
{
now[j]=max(now[j-1]+a[j],pre[j-1]+a[j]);
//now[j]有两种来源,一种是直接在第i个子段之后添加a[j]
//一种是是a[j]单独成为1个子段
pre[j-1]=Max; //更新pre使得pre是前j-1个中最大子段和
Max=max(Max,now[j]);
}
}
printf("%d\n",Max);
}
return 0;
}