【每日一题】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. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴