Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 3160 --硬币问题
3160: 硬币问题
警告!
题目
状态
题解
题目描述
给定 $N$ 种硬币,其中第 $i$ 种硬币的面值为 $a_i$,共有 $C_i$ 个。从中选出若干个硬币,把面值相加,若结果为$S$ ,则称“面值 $S$ 能被拼成”。求 $1$ 到 $M$ 之间能被拼成的面值有多少个。
输入
输入包含多组测试数据。 每组测试数据第一行包含两个整数 $N$ 和 $M$。 第二行包含$2N$个整数,分别表示 $A_1,A_2,\cdots,A_N$ 和 $C_1,C_2,\cdots,C_N$。 当输入 $N=0,M=0$ 时,表示输入终止,且该数据无需处理。
输出
每组数据输出一行答案。
样例输入输出
输入#1
复制
3 10 1 2 4 2 1 1 2 5 1 4 2 1 0 0
输出#1
复制
8 4
提示
对于 $100\%$ 的数据,$1 \leq N \leq 100$,$1 \leq M \leq 10^5$,$1 \leq A_i \leq 10^5$,$1 \leq C_i \leq 1000$。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
普及+/提高-
标签
背包
点击显示
if ($pr_flag) { ?>
递交数
13
已通过
10
} ;?>
通过率
77%
时间限制
1 秒
内存限制
64 MB
来源
HDU 2844
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和