最大M子段和 51Nod - 1052

本文主要是介绍最大M子段和 51Nod - 1052，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.51nod.com/Challenge/Problem.html#!#problemId=1052

dp[i][j]代表第i个子段以a[j]结尾

转移方程dp[i][j]=max{dp[i][j-1],dp[i-1][k]}+a[j] (i-1<=k<=j-1)

对于从i-1个子段转移过来的这一部分 可以搞个前缀和 这样时间复杂度为n*m 但空间还是比较紧 发现只有相邻两个子段才有递推关系 换成滚动数组就好了

 

 

 

 

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=0x3f3f3f3f3f3f3f3f;
const int maxn=5e3+10;ll dp[2][maxn],maxx[2][maxn];
ll ary[maxn];
int n,m;int main()
{ll ans;int i,j,cnt;scanf("%d%d",&n,&m);ans=0,cnt=0;for(i=1;i<=n;i++){scanf("%lld",&ary[i]);if(ary[i]>0) ans+=ary[i],cnt++;}if(m>=cnt)  printf("%lld\n",ans);else{for(i=1;i<=m;i++){for(j=2*i-1;j<=n;j++){dp[i%2][j]=dp[i%2][j-1]+ary[j];dp[i%2][j]=max(dp[i%2][j],maxx[(i-1+2)%2][j-1]+ary[j]);maxx[i%2][j]=max(maxx[i%2][j-1],dp[i%2][j]);}}ans=-N;for(i=m;i<=n;i++) ans=max(ans,dp[m%2][i]);printf("%lld\n",ans);}return 0;
}

 

这篇关于最大M子段和 51Nod - 1052的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---