不是,出大问题,看我上一篇文章,刚写的分组背包,然后比赛就不会了?
好吧,其实比赛一眼就看出是分组背包了, 就是细节上不太会处理.
题意
总共要买K个东西,告诉你了在每个商店买从1到M个商品的价格。但是每个商店只能有一种选择。问你买K个东西的最低价格。
思路
很显然的分组背包了。但是需要求的是最小值,不是最大值,因此我们初始化的时候需要设成inf,而不是0。 同时我们需要知道转移方程dp[j] = min(dp[j], dp[j - k] + $a[i][k]$)
1 |
|
云腾致雨,露结为霜
不是,出大问题,看我上一篇文章,刚写的分组背包,然后比赛就不会了?
好吧,其实比赛一眼就看出是分组背包了, 就是细节上不太会处理.
总共要买K个东西,告诉你了在每个商店买从1到M个商品的价格。但是每个商店只能有一种选择。问你买K个东西的最低价格。
很显然的分组背包了。但是需要求的是最小值,不是最大值,因此我们初始化的时候需要设成inf,而不是0。 同时我们需要知道转移方程dp[j] = min(dp[j], dp[j - k] + $a[i][k]$)
1 | #include <iostream> |