Coins
Time Limit: 3000MS | Memory Limit: 30000K | |
Total Submissions: 27686 | Accepted: 9368 |
Description
People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dollar.One day Tony opened his money-box and found there were some coins.He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn't know the exact price of the watch.
You are to write a program which reads n,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay use these coins.
You are to write a program which reads n,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay use these coins.
Input
The input contains several test cases. The first line of each test case contains two integers n(1<=n<=100),m(m<=100000).The second line contains 2n integers, denoting A1,A2,A3...An,C1,C2,C3...Cn (1<=Ai<=100000,1<=Ci<=1000). The last test case is followed by two zeros.
Output
For each test case output the answer on a single line.
Sample Input
3 10 1 2 4 2 1 1 2 5 1 4 2 1 0 0
Sample Output
8 4
题意:
给出 N , M 代表有 N(1 ~ 100) 种钱币,和钱币总和 M (0 ~ 100000)。后给出 N 种钱币的价值 和 对应的数量,现要凑钱币,问能凑出 1 ~ M 中几种钱币,输出这个数。
思路:
DP。设 dp [ j ] 代表要凑足 i 价值的钱币最多剩下的钱币数。
1. dp [ j ] = m [ i ] ,当 dp [ j ] >= 0 时;
2. dp [ j ] = -1,当 j < v [ i ] || dp [ j - v[ i ] ] <= 0 时;
3. dp [ j ] = dp [ j - v [ i ] ] - 1,其他情况。
初始化时,dp 都为 -1,标记为都不可到达状态,只有 dp [ 0 ] = 0,代表可以到达。若初始化为 0,则只会一直执行 1 公式,最终所有的钱币都能凑成,明显不对。
dp 过程中,曾经到凑成过的钱币知道最后循环循环结束都是能到达的,至于不能到达的,中途通过式子 3 可以更新得到。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n, m, ans; int v[105], num[105]; int dp[100005]; void solve() { memset(dp, -1, sizeof(dp)); dp[0] = 0; for (int i = 1; i <= n; ++i) { for (int j = 0; j <= m; ++j) { if (dp[j] >= 0) dp[j] = num[i]; else if (j < v[i] || dp[j - v[i]] <= 0) dp[j] = -1; else dp[j] = dp[j - v[i]] - 1; } } for (int i = 1; i <= m; ++i) if (dp[i] >= 0) ++ans; } int main() { while (~scanf("%d%d", &n, &m) && (n + m)) { ans = 0; for (int i = 1; i <= n; ++i) { scanf("%d", &v[i]); } for (int i = 1; i <= n; ++i) { scanf("%d", &num[i]); } solve(); printf("%d\n", ans); } return 0; }
相关推荐
coins-security-1.0jar包
2019 Standard Catalog of World Coins, 2001-Date, 13th edition
I = imread( C:\MATLAB701\toolbox\images\imdemos\coins.png ) imshow(I) figure, imhist(I,64)
动态规划题解coins.cpp
poj 3260 The Fewest Coins.md
coins.aca056c6.css
# dp[i] = min{dp[i - coins[j]] + 1}, 且 其中 i >= coins[j], 0 <= j < coins.length # 回溯法,输出可找的硬币方案 # path[i] 表示经过本次兑换后所剩下的面值,即 i - path[i] 可得到本次兑换的硬币值。 ...
COINS 编译器基础架构为 Intel x86、Sparc、Arm、Mips、PowerPC 等提供模块化的编译器组件,例如 C 前端、Fortran 前端、优化器、并行器和后端,以便编译器开发人员可以轻松构建自己的通过组合或修改组件或添加新...
Coins
资源分类:Python库 所属语言:Python 资源全名:Coins-0.1.11.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
Fifa coin auto buyer
资源来自pypi官网。 资源全名:py_aiger_coins-3.3.0-py3-none-any.whl
资源来自pypi官网。 资源全名:football-strike-hack-cheats-coins-2.0.3-2.0.2.tar.gz
基于MFC的画硬币小程序 提供菜单 快捷键 属性栏等选项 简单 代码易懂
硬币从给定的图像中检测硬币并输出它们的总和。 需要各种python模块,例如numpy、OpenCV、PIL。假设图像中至少有两种硬币。 这需要计算出每枚硬币的相对大小,进而用于对它是哪种硬币进行分类。...
coins_counter 基于Matlab和机器视觉的硬币计数系统 Coin counting system based on machine vision and Matlab 描述 用手机拍摄得到一堆硬币图片(详见coin_images文件夹内的示例图片),通过机器视觉的相关知识,...
get-the-coins
tca-flip-coins