【每日一题】4月28日题目精讲 贪心+背包

题号 NC14704
名称 美味菜肴
来源 中国矿业大学(北京)第二届ACM程序设计公开赛(决赛)
戳我进入往期每日一题汇总贴~
往期每日一题题单

图片说明

如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情

题解

每个食物的美味度其实是只和他完成的时间点有关的,所以我们可以考虑在每一个时刻枚举当前完成的是哪一个菜肴,但是这样前面做了哪些菜也需要记下来,一看n的范围显然不可能。
我们可以观察在第t时刻完成第i道菜的美味值的公式,你会发现,如果我们有两道菜肴x和y制作时间相邻,那么交换xy不影响前面的菜和后面的菜的美味值,那么我们可以专注考虑xy。
先做x后做y的美味值和为:
先做y后做x的美味值和为:
是做前面所有菜的时间和)
如果我们规定x就是要在y之前做,那么需要满足
化简得到:
也就是说,我们只需要按照菜肴的t/b排序,菜一定会按照这个顺序做。
然后就可以愉快的dp了——f[i][j]前i道菜在第j分钟的时候选一些做完的最大美味值,这个和01背包问题是一样的,考虑第i个菜做还是不做:
愉快解决!

看完邓老师的题解,记得去做题提高呀~
欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目5月5日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴
全部评论
https://blog.nowcoder.net/n/a4a59fa8acde4dd78ce3d4326472dc57
1 回复 分享
发布于 2020-04-27 12:17
https://blog.nowcoder.net/n/c53e0df8ebef4590b07f5bad6dcaf096
点赞 回复 分享
发布于 2020-06-26 15:31
https://blog.nowcoder.net/n/7f364db31aca4bfa92d57f379cda4012
点赞 回复 分享
发布于 2020-05-05 16:27
https://blog.nowcoder.net/n/71f0b6240e7d41a596035cf64940b49b
点赞 回复 分享
发布于 2020-05-04 00:22
https://blog.nowcoder.net/n/724d5511509c43de977a2ed2309c132d
点赞 回复 分享
发布于 2020-05-03 23:45
https://blog.nowcoder.net/n/a8117d03d111459b8b9cc706e95a136b
点赞 回复 分享
发布于 2020-05-01 00:42
https://blog.nowcoder.net/n/580f60497fc14ac1beb68be9e5d8bf2f
点赞 回复 分享
发布于 2020-04-30 13:29
https://blog.nowcoder.net/n/f9cf19a8ed8e4bd69f68bfe9e0ebb2ab
点赞 回复 分享
发布于 2020-04-29 20:49
https://blog.nowcoder.net/n/d363ff1527ed44ffaa98837754509b23
点赞 回复 分享
发布于 2020-04-28 21:49
https://blog.nowcoder.net/n/c5f919700490475489e87be1a6ddfd72
点赞 回复 分享
发布于 2020-04-28 11:38
https://blog.nowcoder.net/n/e18f9b85676d4af0955f803511fbc8ec
点赞 回复 分享
发布于 2020-04-28 09:07
https://blog.nowcoder.net/n/740fb9874e734273b405856fd727fcc8
点赞 回复 分享
发布于 2020-04-28 00:03
https://blog.nowcoder.net/n/d026679f77ff4ebfbbef9658aa177e16
点赞 回复 分享
发布于 2020-04-27 22:11
https://blog.nowcoder.net/n/03a8dab93810462299dec728ab1dc9fc
点赞 回复 分享
发布于 2020-04-27 22:03
https://blog.nowcoder.net/n/21b9f4cf534c4c86aa4410837782a955
点赞 回复 分享
发布于 2020-04-27 21:22
https://blog.nowcoder.net/n/93411c39fa1a487daa7ea04802110140
点赞 回复 分享
发布于 2020-04-27 18:44
https://blog.nowcoder.net/n/0d38565d73314fffa39786f009423cb5
点赞 回复 分享
发布于 2020-04-27 18:13
https://blog.nowcoder.net/n/59152579825b4cfdbe7cc3bdfe396959
点赞 回复 分享
发布于 2020-04-27 16:27
https://blog.nowcoder.net/n/1af043bab88e4a03805c463848b5c09f
点赞 回复 分享
发布于 2020-04-27 14:58
https://blog.nowcoder.net/n/ded1e6ed471646a7b6cf60905f1db289
点赞 回复 分享
发布于 2020-04-27 14:44

相关推荐

不愿透露姓名的神秘牛友
07-22 11:33
点赞 评论 收藏
分享
07-25 10:31
门头沟学院 Java
求问各位大佬,笔试都考点啥
投递科大讯飞等公司10个岗位
点赞 评论 收藏
分享
06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
评论
点赞
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务