Max Sum Plus Plus HDU - 1024

題意：

給你n個數，選m個子段，各個子段連續且不相交，長度可以為1，設maxn為各個子區間的和，求最大的maxn。

題解：

設dp[i][j]表示前j個數分成i段的最大值
對于第j個數，他可以加入到已有的第i段，也可以自己成為第i段的開始，因此得到狀態轉移為：
dp[i][j]=max(dp[i][j-1],dp[i-1][k])+a[j]
(0<k<j)，,dp[i-1][k]取最大值，k相當于第i-1段的結束位置，二維的話n太大存不下，我們需要繼續優化，dp[i-1][k] + a[j](0 < k < j) 這一項可以另外開一個一維數組tmp[k]記錄一下上一層的前綴最大值（dp[i-1][k]的最大值，0<k<j）,這樣就優化成一維
dp[j]=max(dp[j-1],tmp[j-1])+a[j];
tmp[j-1]表示上一層的最大值

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int INF=0x3f3f3f; const int maxn=1e6+9; int a[maxn]; int dp[maxn]; int tmp[maxn]; int main() {int n,m;while(~scanf("%d %d",&m,&n)){for(int i=1;i<=n;i++)cin>>a[i];}dp[0]=-INF;for(int i=1;i<=m;i++){maxx=-INF;for(int j=i;j<=n;j++){dp[j]=max(dp[j-1],tmp[j-1])+a[j];tmp[j-1]=maxx;maxx=max(maxx,dp[j]);}}cout<<maxx<<endl;}

總結

以上是生活随笔為你收集整理的Max Sum Plus Plus HDU - 1024的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。