博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
51nod 1052 (dp)
阅读量:6095 次
发布时间:2019-06-20

本文共 1466 字,大约阅读时间需要 4 分钟。

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 【分析】dp[j][i]表示从1~i分成j份获得的最大值。
#include 
#define inf 0x3f3f3f3f#define met(a,b) memset(a,b,sizeof a)#define pb push_back#define mp make_pair#define rep(i,l,r) for(int i=(l);i<=(r);++i)#define inf 0x3f3f3f3fusing namespace std;typedef long long ll;const int N = 1e6+5;;const int M = 17;const int mod = 1e9+7;const int mo=123;const double pi= acos(-1.0);typedef pair
pii;int n,m;int a[N];ll dp[2][N];int main(){ scanf("%d%d",&n,&m); met(dp,0); ll sum=0; int cnt=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if(a[i]>0)sum+=a[i],cnt++; } if(m>=cnt)return 0*printf("%lld\n",sum); int now=0; for(int i=1;i<=m;i++){ ll mx=dp[now^1][i-1]; dp[now][i]=mx+a[i]; for(int j=i+1;j<=n-m+i;j++){ mx=max(mx,dp[now^1][j-1]); dp[now][j]=max(mx,dp[now][j-1])+a[j]; } now^=1; } now^=1; ll ans=-99999999999999; for(int i=m;i<=n;i++)ans=max(ans,dp[now][i]); printf("%lld\n",ans); return 0;}

 

转载于:https://www.cnblogs.com/jianrenfang/p/7380310.html

你可能感兴趣的文章
类样式操作
查看>>
Python&HDF5目录
查看>>
Vue -- 双向过滤器去除html标签
查看>>
H5禁止底部横向滚动条,使一个元素居中
查看>>
android 的安全问题
查看>>
skatebroads
查看>>
一些常用的命令和cheat sheet
查看>>
转----------数据库常见笔试面试题 - Hectorhua的专栏 - CSDN博客
查看>>
Android 界面设计 java.lang.NullPointerException 异常的解决方法
查看>>
解决ctrl+shift+F快捷键eclipse格式化与输入法简繁转换冲突问题
查看>>
kali在vbox上运行设置共享文件夹
查看>>
【观点】程序员的七大坏毛病
查看>>
一起谈.NET技术,Mono向Mac OS应用程序开发示好
查看>>
Spring学习(16)--- 基于Java类的配置Bean 之 基于泛型的自动装配(spring4新增)...
查看>>
实验八 sqlite数据库操作
查看>>
四种简单的排序算法(转)
查看>>
Quartz2D之着色器使用初步
查看>>
多线程条件
查看>>
Git [remote rejected] xxxx->xxxx <no such ref>修复了推送分支的错误
查看>>
Porter/Duff,图片加遮罩setColorFilter
查看>>