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

心已赠人 2022-08-03 15:58 141阅读 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;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关字面值常量

字面值常量一个形如 39 的值被称作字面值常量 (literal)，每个字面值常量都对应一种数据类型，字面值常量的形式和值决定了它的数据类型。 1. 整型和浮点型字

蔚落/ 2022年10月31日 05:23/ 0 赞/ 156 阅读

相关【中等】拼 M 面值硬币问题（动态规划）

题目 > 现在有 n1 + n2 种面值的硬币，n1 种为普通面值硬币，可以随意取用。n2 种为纪念币，每种最多只能取一个。每种硬币有一个面值，问：凑满 M 面值有多少种

一时失言乱红尘/ 2022年09月10日 12:11/ 0 赞/ 166 阅读

相关【动态规划】最小硬币面值组合

问题给出硬币种类，及要组合的sum，求用最少的硬币数目到达sum。如：硬币种类1,5,8 sum为20，则最少的硬币数目为5555。解析动态规划解法：

太过爱你忘了你带给我的痛/ 2022年08月09日 15:48/ 0 赞/ 181 阅读

相关【动态规划】硬币面值组合（上台阶）

问题 1分2分5分的硬币三种，组合成1角，共有多少种组合？有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱，有多少中组合可以组成n分钱？

逃离我推掉我的手/ 2022年08月09日 03:16/ 0 赞/ 199 阅读

相关硬币的面值组合个数

[http://www.cnblogs.com/python27/archive/2013/09/05/3303721.html][http_www.cnblogs.com_p

谁借莪１个温暖的怀抱￠/ 2022年08月08日 15:51/ 0 赞/ 193 阅读

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

给定面值为1、2、5的硬币的数量，求不能组成的钱的最小面值。母函数不会，用dp做的，其实就是多重背包。 include<bitset> incl

心已赠人/ 2022年08月03日 15:58/ 0 赞/ 142 阅读

相关 char转换为字面值和ASSCII

//转换为c对应的字面值 String.valueOf(char a) //强转为a对应的ASCII码 int（char a）示例：

- 日理万妓/ 2022年06月05日 08:52/ 0 赞/ 159 阅读

相关 JavaScript判断人民币面值

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Document</

r囧r小猫/ 2022年05月21日 03:05/ 0 赞/ 114 阅读

相关 SpringBoot18：thymeleaf字面值

基本是字符串的拼接，数字类型的计算，以及将取出来的值进行拼接 <h5>字面值</h5> <span th:text="${'thymeleaf'+1}"

今天药忘吃喽~/ 2022年04月25日 10:24/ 0 赞/ 165 阅读

相关整型字面值

整型字面值（常量）是显式地书写的常量，如212 或1776。与C语言相同，C++能够以三种不同的计数方式来书写整数：基数为10、基数为8（老UNIX版本）和基数为16（硬件黑客

小咪咪/ 2021年12月10日 08:13/ 0 赞/ 303 阅读