HDU 1024Max Sum Plus Plus(最大m字段和)-白红宇

动态转移方程：dp[i][j]=max(dp[i-1]+a[i], max(dp[t][j-1])+a[i]) (j-1<=t<i)

表示的是前i个数j个字段和的最大值是多少！

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 10000

using namespace std;

int dp[N][N], num[N];

int main()

{

int n, m, i, j, k;

while(scanf("%d%d", &m, &n)!=EOF)

{

for(i=1; i<=n; i++)

scanf("%d", &num[i]);

memset(dp, 0, sizeof(dp));

for(j=1; j<=m; j++)

for(i=j; i<=n-m+j; i++)

if(i>j)

{

dp[i][j]=dp[i-1][j]+num[i];

for(k=j-1; k<i; k++)//可以用一个Max变量一直更新 j-1 到 i-1 的最大值

dp[i][j]=max(dp[i][j], dp[k][j-1]+num[i]);

}

else dp[i][j]=dp[i-1][j-1]+num[i];

int sum=-1;

for(i=m; i<=n; i++)

if(dp[i][m]>sum)

sum=dp[i][m];

printf("%d\n", sum) ;

}

return 0;

}

时间上优化一下！

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 1000010

using namespace std;

__int64 dp[N][2], num[N];

int main()

{

__int64 n, m, i, j, k, pos;

while(scanf("%I64d%I64d", &m, &n)!=EOF)

{

for(i=1; i<=n; i++)

{

scanf("%I64d", &num[i]);

dp[i][0]=dp[i][1]=0;

}

pos=1;

for(j=1; j<=m; j++)

{

dp[j][pos]=dp[j-1][pos^1]+num[j];

__int64 Max=dp[j-1][pos^1];

for(i=j+1; i<=n-m+j; i++)

{

Max=max(Max, dp[i-1][pos^1]);//这一块直接将 k 的 for循环去掉

dp[i][pos]=max(dp[i-1][pos], Max)+num[i];

}

pos^=1;

}

pos^=1;

__int64 sum=-99999999;

for(i=m; i<=n; i++)

if(dp[i][pos]>sum)

sum=dp[i][pos];

printf("%I64d\n", sum) ;

}

return 0;

}

内存上优化一下，一维数组求解！

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 1000010

using namespace std;

__int64 dp[N], num[N];

int main()

{

__int64 n, m, i, j, k, oldN;

__int64 maxN;//记录dp[k][j-1] (k>=j-1 && k<i) 只有num[i]自己属于第 j 段所有情况的最大值！

while(scanf("%I64d%I64d", &m, &n)!=EOF)

{

for(i=1; i<=n; i++){

scanf("%I64d", &num[i]);

dp[i]=0;

}

for(j=1; j<=m; j++)

{

maxN=max(dp[j-1], dp[j]);// Max = max(dp[j-1][pos^1], dp[j][pos^1])

dp[j]=dp[j-1]+num[j];

for(i=j+1; i<=n-m+j; i++)

{

oldN=dp[i];// 记录 dp[i-1][pos^1]

dp[i]=max(maxN, dp[i-1])+num[i] ;// dp[j][pos] = dp[j-1][pos^1] + num[j]

maxN=max(oldN, maxN);

}

__int64 sum=-99999999;

for(i=m; i<=n; ++i)

if(dp[i]>sum)

sum=dp[i];

printf("%I64d\n", sum) ;

}

return 0;

}

本文转自小眼儿博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3875513.html，如需转载请自行联系原作者