hdu 1024 Max Sum Plus Plus

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; }