hdu 1085 面值为1.2.5的硬币不能组成的最小面值

心已赠人 2022-08-03 15:58 121阅读 0赞

给定面值为1、2、5的硬币的数量，求不能组成的钱的最小面值。

母函数不会，用dp做的，其实就是多重背包。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;
        char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    const int N=10006;
    int a[N];
    int v[4];
    int w[4];
    int num[N]; //开小了
    int main()
    {
    
        while(~scanf("%d",&w[1]))
        {
            w[2]=in(),w[3]=in();
            v[1]=1,v[2]=2,v[3]=5;
            if(w[1]+w[2]+w[3]==0)break;
            mem(a,0);
            a[0]=1;
            for(int i=1;i<=3;i++) //dp多重背包做的
            {
                mem(num,0);
                for(int j=v[i];j<10000;j++) //注意j的开始
                {
                    if(!a[j] && a[j-v[i]] && num[j-v[i]]<w[i])
                    {
                        a[j]=1;
                        num[j]=num[j-v[i]]+1;
                    }
                }
            }
    
            for(int i=1;i<10000;i++)
            {
                if(!a[i])
                {
                    printf("%d\n",i);
                    break;
                }
            }
    
    
        }
        return 0;
    }