之前在書里看過了，但是沒有做過例題，忘記它的原理了

dp[i][j]表示前i個數(shù)中選j段所能構(gòu)成的最大值，（強(qiáng)調(diào)一下，這j段包括最后一個元素[i]的），這樣第i個元素要不跟倒數(shù)第二個一起，要不獨(dú)自形成一段——第j段 dp[i][j]=max(dp[i-1][j], dp[i-len[j]][j-1]+sum) len[j]表示第j段的長度，sum表示長度為len[j]的

當(dāng)然得用優(yōu)化算法，這是優(yōu)化算法是在書里面看到的，挺巧妙的

for(i=1;i<=m;i++){
max=-INF;
for(j=i;j<=n;j++){
dp[j]=maxb(dp[j-1]+num[j],pre[j-1]+num[j]);
pre[j-1]=max;
max=maxb(max,dp[j]);
}

dp指上面的dp[i][j]，pre記錄第j個數(shù)前最大的dp

說說我的看完題解后，自己的敲的代碼錯在哪里吧

for(i=1;i<=m;i++)把這里的m改成n就錯了，因?yàn)檫@里的m是指段數(shù)

for(j=i;j<=n;j++)把這里的j=i改成j=1就錯了，因?yàn)閕段的話，至少都要從第i個數(shù)開始吧

for(i=0;i<=n;i++){pre[i]=0;dp[i]=0;}把這個換成memset（pre），memset（dp）超時(shí)了，畢竟是1000000次嗎，浪費(fèi)太多操作了

貼上我的ACCEPT代碼吧

#include "iostream" #include "string.h" #define INF 9999999; using namespace std; int maxb(int a,int b){return a>b?a:b;} int pre[1000010],dp[1000010],num[1000010];int main(){int m,n,i,j,max;while(cin>>m>>n){for(i=1;i<=n;i++)cin>>num[i];for(i=0;i<=n;i++){pre[i]=0;dp[i]=0;}for(i=1;i<=m;i++){max=-INF;for(j=i;j<=n;j++){dp[j]=maxb(dp[j-1]+num[j],pre[j-1]+num[j]);pre[j-1]=max;max=maxb(max,dp[j]);}}cout<<max<<endl;} }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/dowson/p/3277432.html

總結(jié)

以上是生活随笔為你收集整理的hdu1024Max Sum Plus Plus的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。