首页 > 代码库 > hdu 1024 Max Sum Plus Plus
hdu 1024 Max Sum Plus Plus
题意：最大子序列和加强版，恰好有m个子序列，输出这m个子序列的最大和
分析:先想一下最大子序列和，用dp[i]表示选第i个数的最大和，那么max(dp[i])0<i<=n就是答案
恰好分为m个，那么增加一维表示选第i个并且恰好分为j块的最大和,那么可以轻松得到状态转移方程
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[j];分别表示第i个是单独成块还是和i-1连成一块
显然没法这样空间是不够的，并且恰好分为j块的时候只和恰好分成j-1块的时候有关，那么可以使用滚动数组
或者使用两个数组分别表示上次的结果和本次的结果
#include<bits/stdc++.h>using namespace std;const int maxn=1e6+5;int d[maxn],p[maxn],a[maxn];int main(){ int n,m,res; while(scanf("%d%d",&m,&n)!=EOF){ for(int i=1;i<=n;i++)scanf("%d",&a[i]); memset(d,0,sizeof(d)); memset(p,0,sizeof(p)); for(int i=1;i<=m;i++){ res=INT_MIN; for(int j=i;j<=n;j++){ d[j]=max(d[j-1],p[j-1])+a[j]; p[j-1]=res; res=max(res,d[j]); } } printf("%d\n",res); } return 0; }
hdu 1024 Max Sum Plus Plus
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。