1. 题目

传送门= ̄ω ̄=

题意:给你n种硬币,第i种的面值是ai,个数时ci,求这些硬币能凑成区间$[1,m]$间的那些值

2. 题解

普通的多重背包复杂度为$O(n\times m\times c)$显然超时
二进制优化复杂度大致刚好卡在1e8的复杂度上,多组数据就挂了
只能用$O(n\times m)$的复杂度了

这题又没有背包容量限制,只有每种硬币个数限制
我们循环的第一层枚举使用那种硬币,设fi表示当背包容量为i的时候,当前枚举的物平最少的使用次数,默认都为0。
再设booki表示(全局)能否达到总面值i,等于1表示能,等于0表示不能

如果要从状态i转移到状态j,那么必须满足:
1. booki=1
2. fi+1<=C你当前枚举的物平

如果满足的话就转移状态,并且更新fj的值。注意每次枚举物平的时候要把f全设为0

代码: