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個數(shù)字（包含第j個）分成i段的最大值//dp[i][j]只和dp[i][j-1]和dp[i-1][0~j-1]有關(guān)，用滾動數(shù)組就可以//max(dp[i-1][0]~dp[i][j-1])在計(jì)算的時候就可以順便求出來#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]，當(dāng)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;}新聞熱點(diǎn)
疑難解答
