Coins
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 218 Accepted Submission(s): 80
Problem Description
Whuacmers use coins.They have coins of value A1,A2,A3...An Silverland dollar. One day Hibix opened purse 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
#include<stdio.h> #include<string.h> #define max(a,b) a>b?a:b; int m; int f[100010]; void zero_onepag(int w) { for(int i=m;i>=w;i--) f[i]=max(f[i],f[i-w]+w); } void fullpag(int w) { for(int i=w;i<=m;i++) f[i]=max(f[i],f[i-w]+w); } void allpag(int w,int n) { if(w*n>m)fullpag(w);//如果东西很多,可以当成完全背包 else//否则,当成01背包,用2分优化 { int k=1; while(k<=n) { zero_onepag(k*w); n-=k; k*=2; } zero_onepag(n*w); } } int main() { //freopen("in.txt","r",stdin); int n,i,totle; int w[110],v[110]; while(scanf("%d%d",&n,&m),m||n) { memset(f,0,sizeof(f)); for(i=0;i<n;i++)scanf("%d",&w[i]); for(i=0;i<n;i++)scanf("%d",&v[i]); for(i=0;i<n;i++)if(w[i]<m)allpag(w[i],v[i]); for(i=1,totle=0;i<=m;i++)if(f[i]==i)totle++; printf("%d\n",totle); } 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
2014/01/01 16:24 93,696 Pink Piggy Bank with Money Coins Powerpoint Presentation.ppt 2014/01/01 16:37 97,792 Present Box Powerpoint Presentation .ppt 2014/01/01 16:36 97,280 Red Sphere Disaggregation ...
Coins
COINS 编译器基础架构为 Intel x86、Sparc、Arm、Mips、PowerPC 等提供模块化的编译器组件,例如 C 前端、Fortran 前端、优化器、并行器和后端,以便编译器开发人员可以轻松构建自己的通过组合或修改组件或添加新...
资源分类: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
基于MFC的画硬币小程序 提供菜单 快捷键 属性栏等选项 简单 代码易懂
资源来自pypi官网。 资源全名:football-strike-hack-cheats-coins-2.0.3-2.0.2.tar.gz
硬币从给定的图像中检测硬币并输出它们的总和。 需要各种python模块,例如numpy、OpenCV、PIL。假设图像中至少有两种硬币。 这需要计算出每枚硬币的相对大小,进而用于对它是哪种硬币进行分类。...
coins_counter 基于Matlab和机器视觉的硬币计数系统 Coin counting system based on machine vision and Matlab 描述 用手机拍摄得到一堆硬币图片(详见coin_images文件夹内的示例图片),通过机器视觉的相关知识,...
get-the-coins
tca-flip-coins