【每日一题】5月6日题目精讲 动态规划

五一小长假是补题的好时机!
每日一题五一特别活动:5月1日-5月5日,补之前的每日一题,均可获得牛币奖励(直接发到当日帖子下就可以,之前到期的题目也可以补)我们将在5月7日审核,并发放所有牛币~

发家致富就靠这个假期了!
戳我进入往期每日一题汇总贴~

5月6日题目预告
题号 NC20273
名称 [SCOI2009]粉刷匠
来源 [SCOI2009]
往期每日一题题单

图片说明

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

我们先考虑只有一个木板——求出该木板粉刷x次,能够正确粉刷的格子数!
用f[k][i][j]表示第k 条木板,粉刷i 次,前j 个格子能够正确粉刷的格子数,那么方程是显然的:
f[k][i][j] = max {f[k][i – 1][p] + w[p + 1,][j](, w[l][r]表示l,r段一次粉刷能够正确粉刷的格子数)
然后我们就可以进行第二次动态规划:利用上一次的结果,求出所有木板粉刷y次,能够正确粉刷的格子数————
实际这是一个分组背包问题——将每条木板看成一个物品组,则物品组中每个物品的费用c[i]和价值w[i]分别为x和f[k][x][M]。所求为从每组中最多选一件,选哪些物品装入背包可使这些物品的费用总和不超过背包容量T,且价值(粉刷正确的格子数)总和最大。
这个题告诉我们,dp一遍不行了可以多dp一遍哈哈哈。

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

活动奖励:

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

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

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴
全部评论
https://blog.nowcoder.net/n/4a2e01116061401d83ce57dfbc3feafc
1 回复 分享
发布于 2020-05-02 12:05
https://blog.nowcoder.net/n/53d68d60653845f4ab40af7ccbe5025a
1 回复 分享
发布于 2020-05-07 11:31
五月一日题目怎么有两个!
点赞 回复 分享
发布于 2020-05-01 10:07
清楚姐姐补得题的博客链接是发在这里吗
点赞 回复 分享
发布于 2020-05-01 10:54
https://blog.nowcoder.net/n/b05c5064b7ff44618113b63cc4c202e4
点赞 回复 分享
发布于 2020-05-01 11:45
清楚姐姐假期快乐
点赞 回复 分享
发布于 2020-05-01 15:56
https://blog.nowcoder.net/n/006c416911574cb6a3c0c2363ecf6888
点赞 回复 分享
发布于 2020-05-01 17:00
https://blog.nowcoder.net/n/e66e1bfdef9d417aae4a3e3ef413c224
点赞 回复 分享
发布于 2020-05-02 15:30
https://blog.nowcoder.net/n/93024f0ad5a54ed28ba578fbf827783d
点赞 回复 分享
发布于 2020-05-02 16:44
https://blog.nowcoder.net/n/830fb917213f4c38963f5cca00e02f76
点赞 回复 分享
发布于 2020-05-03 22:58
https://blog.nowcoder.net/n/c919d633f0a642eda335e465757c30bd
点赞 回复 分享
发布于 2020-05-05 16:16
https://blog.nowcoder.net/n/3c06a467b7ba4dfabd2bf27f96d8c24c
点赞 回复 分享
发布于 2020-05-06 21:43
https://blog.nowcoder.net/n/b8dc67b2964845a1acaf69fe3473e0e3
点赞 回复 分享
发布于 2020-05-06 23:15
清楚姐姐,请问一下是之前从第一篇3.25开始的每日一题补写题解有奖励吗?
点赞 回复 分享
发布于 2020-05-07 11:50
https://blog.nowcoder.net/n/3f783cc49dec4bdea1c6b445716c4bb3
点赞 回复 分享
发布于 2020-05-07 19:06
https://blog.nowcoder.net/n/df6605df8fe34afb92d1340e5f1b2bcb
点赞 回复 分享
发布于 2020-05-07 22:10
https://blog.nowcoder.net/n/7de91be7747540c6b0e5967146dfb5ed
点赞 回复 分享
发布于 2020-05-07 22:57
https://blog.nowcoder.net/n/7867b64e8ba84517aaef4b3ea6b5ba28
点赞 回复 分享
发布于 2020-05-08 00:10
https://blog.nowcoder.net/n/2aa0732f49414e85ae687b092d68e15d
点赞 回复 分享
发布于 2020-05-08 22:22
https://blog.nowcoder.net/n/211bb97cb2f14d3ca44a969d0129556a
点赞 回复 分享
发布于 2020-05-09 20:50

相关推荐

02-01 19:48
门头沟学院 Java
神哥了不得:(非引流)直接暑期吧,没时间日常了,老鱼简历把水印去了,或者换个模板,简历字体大小都不太行,建议换2个高质量的项目,面试应该还会再多一些
点赞 评论 收藏
分享
会飞的猿:我看你想进大厂,我给你总结一下学习路线吧,java语言方面常规八股要熟,那些java的集合,重点背hashmap八股吧,jvm类加载机制,运行时分区,垃圾回收算法,垃圾回收器CMS、G1这些,各种乐观锁悲观锁,线程安全,threadlocal这些。在进阶一些的比如jvm参数,内存溢出泄漏排查,jvm调优。我这里说的只是冰山一角,详细八股可以去网上找,这不用去买,都免费资源。mysql、redis可以去看小林coding,我看你简历上写了,你一定要熟,什么底层b+树、索引结构、innodb、mvcc、undo log、redo log、行级锁表级锁,这些东西高频出现,如果面试官问我这些我都能笑出来。消息队列rabbitmq也好kafka也好,学一种就行,什么分区啊副本啊确认机制啊怎么保证不重复消费、怎么保证消息不丢失这些基本的一定要会,进阶一点的比如LEO、高水位线、kafka和rocketmq底层零拷贝的区别等等。计算机网络和操作系统既然你是科班应该理解起来问题不大,去看小林coding这两块吧,深度够了。spring boot的八股好好看看吧,一般字节腾讯不这么问,其他的java大厂挺爱问的,什么循环依赖啥的去网上看看。数据结构的话科班应该问题不大,多去力扣集中突击刷题吧。项目的话其实说白了还是结合八股来,想一想你写的这些技术会给你挖什么坑。除此之外,还有场景题、rpc、设计模式、linux命令、ddd等。不会的就别往简历上写了,虽然技术栈很多的话好看些,但背起来确实累。总结一下,多去实习吧,多跳槽,直到跳到一个不错的中厂做跳板,这是一条可行的进大厂的路线。另外,只想找个小厂的工作的话,没必要全都照这些准备,太累了,重点放在框架的使用和一些基础八股吧。大致路线就这样,没啥太多难度,就是量大,你能达到什么高度取决于你对自己多狠,祝好。
点赞 评论 收藏
分享
评论
2
1
分享

创作者周榜

更多
牛客网
牛客企业服务