Coins （poj 1742 && hdu 2844 DP）-白红宇

Coins （poj 1742 && hdu 2844 DP）

阅读量：6078 次

发布时间：2019-06-20

本文共 2216 字，大约阅读时间需要 7 分钟。

Language: Default

Coins

Time Limit: 3000MS		Memory Limit: 30000K
Total Submissions: 30047		Accepted: 10195

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.

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 101 2 4 2 1 12 51 4 2 10 0

Sample Output

Source

题意：给n张不同面值的钱，每种面值的钱都有一定数量，问用这些钱可以凑出多少种不同的面值，而且面值要在1~m内。输出种数。

思路：dp[i]表示i面值的钱是否可以凑出来（0或1）。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                #pragma comment (linker,"/STACK:102400000,102400000")#define maxn 100005#define MAXN 2005#define mod 1000000009#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FRL(i,a,b) for(i = a; i < b; i++)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n) scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pf printf#define DBG pf("Hi\n")typedef long long ll;using namespace std;int n,m;int dp[maxn],num[maxn];int v[111],c[111];int main(){ int i,j; while (sff(n,m)&&(n+m)) { mem(dp,0); FRL(i,0,n) sf(v[i]); //v[i]存的面值 FRL(i,0,n) sf(c[i]); //c[i]存的每一个面值相应的数量 int ans=0; dp[0]=1; FRL(i,0,n) { mem(num,0); //num[j]表示凑够面值j时用了多少v[i]面值的钱 FRE(j,v[i],m) { if (!dp[j]&&dp[j-v[i]]&&num[j-v[i]]

转载地址：http://ykhgx.baihongyu.com/

你可能感兴趣的文章