当前位置:首页 > 动态规划 > 背包 > 正文
洛谷P6567买表(NOIOnline第三场入门组C)
406+

题目大意:n种钱币,面值分别是$a_i$元,各有$b_i$张,请问能否组成k元?m个询问哦!

题目描述

Jimmy 到 Symbol 的手表店买手表,Jimmy 只带了 $n$ 种钱币,第 $i$ 种钱币的面额为 $k_i$ 元,张数为 $a_i$ 张。Symbol 的店里一共有 $m$ 块手表,第 $i$ 块手表的价格为 $t_i$ 元。

Symbol 的手表店不能找零,所以 Jimmy 只能在凑出恰好的钱数时才能购买一块手表。现在对于店里的每块手表,Jimmy 想知道他能不能凑出恰好的钱数进行购买。

输入输出格式

输入格式

第一行两个空格分隔的整数 $n$ 和 $m$ 表示钱币数与手表数。

接下来 $n$ 行每行两个空格分隔的整数 $k_i$ 和 $a_i$ 表示钱币的面额和张数。

第 $n+2$ 行,共 $m$ 个用空格分隔的整数 $t_i$,表示每块手表的价格。

输出格式

一共 $m$ 行,对于第 $i$ 行,如果能凑出恰好的钱数购买第 $i$ 块手表则输出 `Yes` 否则输出 `No`,注意只有首字母大写。

输入输出样例

输入样例 #1

3 5
1 2
5 1
6 3
3 19 21 1 7

输出样例 #1

No
Yes
No
Yes
Yes

说明

样例 1 解释

– 第二块手表 $19=6 \times 3+1=6 \times 2+5+1 \times 2$,可以恰好凑出。
– 第四块手表 $1=1 \times 1$,可以恰好凑出。
– 第五块手表 $7=5+2\times 1=6 \times 1+1$,可以恰好凑出。

数据规模与约定
– 对于 $50\%$ 的数据,保证 $n\leq 10$,$m \leq 60$,$a_i \leq 20$,$k_i \leq 5000$,$t_i \leq 250$。
– 对于 $100\%$ 的数据,保证 $1 \leq n \leq 200$,$1 \leq m \leq 10^5$,$1 \leq a_i \leq 1000$,$1 \leq k_i \leq 500000$,$0 \leq t_i \leq 500000$。

解题思路

询问很多,显然是预处理后逐个回答!

这是一个混合背包,每种钱币就是一个物品,可以不选,也可以选1件、多件。

对于n个物品,最大容量为m,平均数量是c,总数量是k,若直接求,时间复杂度是O(m*k)必定超时。

可以使用二进制优化,这样复杂度就降低到$O(n*log_2c*m)$,容易超时。

如果用“单调队列”优化的思想,可以降低时间复杂度至O(n*m),勉强可以过。

程序实现

对每个物品进行二进制拆分,如物品有14个,可以拆分成1、2、4、7四种物品,这四种物品的01选择,可以组成0-14,相当于一个数量14的物品选择0-14。

运用了单调队列优化多重背包的思想。只要选择个数不超过b个,就可以像完全背包一样从下往上更新。从下往上更新,如价值为3的物品,那么价值3受0影响,价值6只受0、3影响,价值9只受0、3、6影响……价值120f[120]只受117、114、111等影响,不会被119、118、116、115等更新。我从下往上转移的时候,顺便记录当前的“最大值”——最靠后的“1”,也就是最后能实现的面值。前面的面值没后面的面值好,因为前面的能更新,后面的肯定也能更新!最后就是判断“是不是过期”,能不能通过“b个a”转移过来。

更多

About

坚决不Copy代码!

本文标签:,,,,,,,

洛谷P6567买表(NOIOnline第三场入门组C):等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter