首页 > 代码库 > 51nod1052 最大M子段和
51nod1052 最大M子段和
dp优化我总是不太熟练。这一次首先我写了O(n4)->O(n3)->O(n2)。一步步的优化过来。yyl好像用的是单调队列优化dp我看不懂他的代码。。。
O(n4)
#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))#define ll long longll read(){ ll x=0,f=1;char c=getchar(); while(!isdigit(c)) { if(c==‘-‘) f=-1;c=getchar(); } while(isdigit(c)) x=x*10+c-‘0‘,c=getchar(); return x*f;}const int nmax=5e3+5;const ll inf=1e18;ll dp[nmax],g[nmax],sm[nmax];int main(){ int n=read(),m=read();ll u,v,d; rep(i,1,n) sm[i]=sm[i-1]+read(); rep(i,1,m) { rep(j,i,n) { rep(k,0,j-1) { u=inf; rep(t,k+1,j) u=min(u,sm[t]); dp[j]=max(dp[j],g[k]+sm[j]-u); } } rep(j,1,n) g[j]=dp[j]; } ll ans=0; rep(i,m,n) ans=max(ans,dp[i]); printf("%lld\n",ans); return 0;}O(n3)
#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))#define ll long longll read(){ ll x=0,f=1;char c=getchar(); while(!isdigit(c)) { if(c==‘-‘) f=-1;c=getchar(); } while(isdigit(c)) x=x*10+c-‘0‘,c=getchar(); return x*f;}const int nmax=5e3+5;const ll inf=1e18;ll dp[nmax],g[nmax],sm[nmax];int main(){ int n=read(),m=read();ll u,v,d,tm=0,cnt=0; rep(i,1,n) { sm[i]=sm[i-1]+(u=read()); if(u) ++cnt,tm+=u; } if(m>=cnt) { printf("%lld\n",tm);return 0; } rep(i,1,m) { rep(j,i,n) { dp[j]=dp[j-1]; rep(k,0,j-1) dp[j]=max(dp[j],g[k]+sm[j]-sm[k]); } rep(j,1,n) g[j]=dp[j]; } printf("%lld\n",dp[n]); return 0;}O(n2)
#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))#define ll long longll read(){ ll x=0,f=1;char c=getchar(); while(!isdigit(c)) { if(c==‘-‘) f=-1;c=getchar(); } while(isdigit(c)) x=x*10+c-‘0‘,c=getchar(); return x*f;}const int nmax=5e3+5;const ll inf=1e18;ll dp[nmax],sm[nmax],f[nmax];int main(){ int n=read(),m=read();ll u,v,d,tm=0,cnt=0; rep(i,1,n) { sm[i]=sm[i-1]+(u=read()); if(u) ++cnt,tm+=u; } if(m>=cnt) { printf("%lld\n",tm);return 0; } f[0]=-inf;rep(j,1,n) f[j]=max(f[j-1],dp[j-1]-sm[j-1]); rep(i,1,m) { rep(j,i,n) dp[j]=max(dp[j-1],f[j]+sm[j]); f[0]=-inf;rep(j,1,n) f[j]=max(f[j-1],dp[j-1]-sm[j-1]); } printf("%lld\n",dp[n]); return 0;}
1052 最大M子段和
基准时间限制：2 秒 空间限制：131072 KB 分值: 80 难度：5级算法题
收藏
关注N个整数组成的序列a[1],a[2],a[3],…,a[n]，将这N个数划分为互不相交的M个子段，并且这M个子段的和是最大的。如果M >= N个数中正数的个数，那么输出所有正数的和。
例如：-2 11 -4 13 -5 6 -2，分为2段，11 -4 13一段，6一段，和为26。
Input
第1行：2个数N和M，中间用空格分隔。N为整数的个数，M为划分为多少段。（2 <= N , M <= 5000)第2 - N+1行：N个整数 (-10^9 <= a[i] <= 10^9)
Output
输出这个最大和
Input示例
7 2-211-413-56-2
Output示例
26
51nod1052 最大M子段和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。