文档章节

[ 题解 ] [ 动态规划 ] B. Teamwork

o
 osc_ik0wlz7f
发布于 2019/03/15 22:42
字数 415
阅读 18
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

http://codeforces.com/group/NVaJtLaLjS/contest/238203/problem/B


题意:

农夫让牛来包装礼物,N只牛有各自的能力值。

相邻K只牛可以组成一个小组,小组内牛的能力全会提高到与小组内最高的能力值相等。

现在问,这些牛怎么分组,可以得到最大的能力值总和。

(题目没有要求每个小组必须有K只牛)


示例:

Input 

7 3
1
15
7
9
2
5
10 

Output

84


最开始我是没有注意到!相邻!这个条件的,用了最强带最弱的贪心策略,WA到最后才发现条件......


对于一只牛,能组队的只有相邻K-1只;

对第n牛检查相邻的牛中的最大值,然后乘K累加入dp数组。

如果在n+1只牛检查到更大的值,dp数组会被相应地刷新;

反过来,如果第n+1只牛相邻的牛并没有这么强,那么dp数组就不会被更新。


最终,dp数组存的是最好的组队策略得到的能力值总和,输出结果就可以了。

 

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 int N=0,K=0;
 5 int cows[10002]={0};
 6 int dp[10002]={0};
 7 
 8 int max(int a,int b)
 9 {
10     if(a>b)return a;
11     else return b;
12 }
13 int main()
14 {
15     scanf("%d%d",&N,&K);
16     for(int n=1;n<=N;n++)
17     {
18         scanf("%d",&cows[n]);
19     }
20     
21     for(int n=1;n<=N;n++)
22     {
23         int MAX=cows[n];
24         for(int k=1;k<=K;k++)
25         {
26             dp[n+k]=max( dp[n+k],dp[n]+k*MAX);
27             MAX=max(MAX,cows[n+k]);
28         }
29     }
30     
31     printf("%d\n",dp[N]);
32     return 0;
33 }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
C++模板库--C++ B-tree

这是一个google开源的C++模板库,实现了基于B-tree数据结构的有序内存容器。类似于STL的map、set、multimap和multiset模板,C++ B-tree也提供了btreemap、btreeset、btreemultimap和btreemu...

匿名
2013/02/05
3.4K
1
同步,异步,阻塞,非阻塞的Java例子

定义:任务A,任务B 同步:任务A和任务B之间有关联,例如任务B中途要给任务A一个数字,那么任务A或许需要等待任务B生产这个数,任务A需要等待任务B的这个动作叫做同步。 异步:事件A和事件B...

JoshuaShaw
2016/03/30
2.9K
2
搞定编程大赛必知哪10个算法?

再没有比算法更让人头疼的东西了吧! 前两天参加了一个编程大赛http://www.ijiami.cn/newsInfo?id=519&v=2,有感于算法,所以整理了这篇关于编程竞赛的10个算法。 动态规划(DP)似乎占据了大...

小开2014
2014/10/22
396
6
【难题】原创的难点。。求解

问下 3个变量 $a $b $c ,各自返回是int数字 不确定。 举例,$a=3 $b=5 $c=2 需求,首页有一个列表 共需要展示5条数据, 权重这样划分 $b>$c>$a 也就是说 如果$b返回数据有5条 或者大于5条 ...

kacc850
2017/09/06
109
3
B+树磁盘存储 CRUD - B+Tree

B+Tree 是一个基于 Posix 的数百万(甚至数十亿)key-value 存储的最小B+树实现。 Demo ./demobuild.sh 代码覆盖测试 注意:需要先删除现有的 以进行此测试! ./coveragebuild.sh...

我的上铺叫路遥
2018/01/28
735
0

没有更多内容

加载失败,请刷新页面

加载更多

PPDet:减少Anchor-free目标检测中的标签噪声,小目标检测提升明显

本文转载自AI算法修炼营。 这篇文章收录于BMVC2020,主要的思想是减少anchor-free目标检测中的label噪声,在COCO小目标检测上表现SOTA!性能优于FreeAnchor、CenterNet和FCOS等网络。整体思路...

我爱计算机视觉
昨天
0
0
BIO、NIO、AIO 区别和应用场景

点击上方“ java1234 ”,选择“标星公众号” 优质文章,第一时间送达 66套java从入门到精通实战课程分享...

小锋2
今天
0
0
ContentProvider(查询 插入 修改 删除 )

注意 本篇实在sqlite的基础上编写的所以建议首先了解sqlite 首先建立两个模块 ContentProvider ContentResolver ContentProvider 里面需要建立表和建立连接 所以在这里需要建立DBHelp类 DBHe...

osc_6ttvlt1w
10分钟前
7
0
用这个网站一查,才知道自己被卖了

还记得上个月好多大佬的Twitter账号被盗用于网络诈骗的事件吗。 7月15日,美国前总统奥巴马、“股神”巴菲特、特斯拉CEO马斯克、微软创始人比尔·盖茨等人的账户连续“被登录”,用来向大众诈...

猿大白
今天
0
0
牛客多校第9场E Groundhog Chasing Death

开始以为是什么高深的数论题,后来 重新 推了一下,得到了个这么个式子。 ∏ i = a b ∏ j = c d ( p 1 m i n ( a 1 [ 1 ] i , a 2 [ 1 ] j ) p 2 m i n ( a 1 [ 2 ] i , a 2 [ 2 ] j ) . . ...

osc_wdq5dwoy
11分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部