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<=n<=100),m(m<=100000),第二行包含2n个整数,
表示a1,a2,a3…an,c1,c2,c3…cn(1<=ai<=100000,1<=ci<=1000)。
最后一个测试用例后面跟着两个零。
思路:典型的男人八题。具体思路详见代码。
1 #include <cstdio> 2 #include <fstream> 3 #include <algorithm> 4 #include <cmath> 5 #include <deque> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <cstring> 10 #include <map> 11 #include <stack> 12 #include <set> 13 #include <sstream> 14 #include <iostream> 15 #define mod 1000000007 16 #define ll long long 17 using namespace std; 18 19 int n,m; 20 int a[105],b[105]; 21 int dp[100005];// 22 int main() 23 { 24 while(scanf("%d %d",&n,&m)&&n!=0) 25 { 26 for(int i=0;i<n;i++)//硬币价值 27 { 28 scanf("%d",&a[i]); 29 } 30 for(int i=0;i<n;i++)//每种硬币的数量 31 { 32 scanf("%d",&b[i]); 33 } 34 memset(dp,-1,sizeof(dp));//dp[i] >= 0 表示价值i可以被凑齐,而 dp[i] = -1 ,表示无法凑齐 35 dp[0]=0;//表示价值为0 的不需要任何银币,所以其值为0 36 for(int i=0;i<n;i++)//n种硬币 37 { 38 for(int j=0;j<=m;j++)//枚举价值,检验是否某一价值可以利用 第 i 个银币转移而来 39 { 40 if(dp[j]>=0)//这意味着这个价值已经被找到,不需要判断是否可以凑齐 41 { 42 dp[j]=b[i];//表示这一状态还剩下可以用于转移的银币数量,不过这是初始设定的,已经凑齐的价值可以通过加上若干个第i中银币找到下一个可以凑齐的价值 43 } 44 //前一个条件表示剩余价值不能再加上一个该种银币以实现状态转移 45 //后一个条件表示用了这个价值的银币用完了,或者用之前的状态凑不齐,没有根基,转移不起 46 //也就是上一个状态不能实现,那么在上一状态的基础上加上银币,不能保证目前状态可以实现。 47 //dp[j]的值表示还可以使用第i中银币数,银币数不足的时候自然不能继续转移下去 48 //对于这种清空,此时 dp[ j- a[i]]的值为0 ,则转移后dp[j]的值变为-1,表示无法凑成 49 else if(j<a[i]||dp[j-a[i]]<=0) 50 { 51 dp[j]=-1;//表示无法实现 52 } 53 //执行到了这一步,满足条件: 54 //1:这一价值还没有被确定可以凑齐,dp[j]在复制之前值为-1 55 //2:用价值为a[i] 的银币,凑成价值为j的状态是存在的,也就是有路可以继续走下的意思 56 //3:此时的j一定可以被凑齐 57 else 58 { 59 dp[j]=dp[j-a[i]]-1; 60 } 61 } 62 } 63 int ans=0; 64 for(int i=1;i<=m;i++) 65 { 66 if(dp[i]>=0) 67 { 68 ans++; 69 } 70 } 71 printf("%d\n",ans); 72 } 73 }