hdu 1024 Max Sum Plus Plus

2019-11-06 06:35:33

字体：大中小

来源：转载

供稿：网友

dp一直不太会，练练dp 参考题解：http://www.cnblogs.com/kuangbin/archive/2011/08/04/2127085.html http://www.cnblogs.com/dongsheng/archive/2013/05/28/3104629.html 我的理解都在注释里面

//dp[i][j] = max(dp[i][j-1],max(dp[i-1][0]~dp[i-1][j-1]))+num[i]//dp[i][j]表示前j个数字（包含第j个）分成i段的最大值//dp[i][j]只和dp[i][j-1]和dp[i-1][0~j-1]有关，用滚动数组就可以//max(dp[i-1][0]~dp[i][j-1])在计算的时候就可以顺便求出来#include <cstdio>#include <cstring>#include <algorithm>const int INF = 99999999;const int MAXN = 1000010;int num[MAXN],dp[MAXN],PRe[MAXN];int main(){ int m,n,temp; while(scanf("%d %d",&m,&n) != EOF) { for(int i = 1; i <= n; ++i) scanf("%d",&num[i]); memset(dp,0,sizeof(dp)); memset(pre,0,sizeof(pre)); for(int i = 1; i <= m; ++i) { temp = -INF; //dp[i][j]，当j=i-1时,i-1个元素分成i段显然是不行的,所以j=i for(int j = i; j <= n; ++j) { dp[j] = std::max(dp[j-1], pre[j-1]) + num[j]; //temp是j-1（包括第j-1个）之前的最大值 pre[j-1] = temp; temp = std::max(temp,dp[j]); } } printf("%d/n",temp); } return 0;}

上一篇：PAT 1008

下一篇：bzoj4034