关于硬币的近10条评论(全部评论)
二进制拆分秒了，其实一般来说二进制拆分不用单独拆，在扫描的时候顺便拆了就行增强型图元文件 2024-04-09 11:19 1楼

1774. [POJ 1742]硬币

★★☆ 输入文件：makecoins.in 输出文件：makecoins.out 简单对比
时间限制：3 s 内存限制：256 MiB

给定 N 种硬币，其中第 i 种硬币的面值为 Ai，共有 Ci 个。

从中选出若干个硬币，把面值相加，若结果为 S，则称“面值 S 能被拼成”。

求 1∼M 之间能被拼成的面值有多少个。

输入包含多组测试用例。

每组测试用例第一行包含两个整数 N 和 M。

第二行包含 2N 个整数，分别表示 A1,A2,…,AN 和 C1,C2,…,CN。

当输入用例 N=0，M=0 时，表示输入终止，且该用例无需处理。

每组用例输出一个结果，每个结果占一行。

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

8
4

1≤N≤100,1≤M≤10^5,1≤Ai≤10^5,1≤Ci≤1000。