首页 > 其他分享 >1961: 硬币组合

1961: 硬币组合

时间:2022-10-13 22:56:32浏览次数:50  
标签:组合 硬币 int min 1961 钞票 freopen 0x3f3f3f3f

 

 这道题目是一道经典的DP:

讲一下思路:

f[i]:指i元可以用最少多少张钞票凑齐,凑不齐的话值为-1

先将f数组初始化为无穷大(因为后面有min操作所以不能用-1)

输入的同时将f[a[i]]设为1(举个例子:有一张五元的钞票要凑5元,可以只用一张钞票完成任务)

将f[0]设为0(又一个初始化)

再来一个n2的双重i j 循环,i从1到s 表示要凑齐i元,j从1到n表示遍历一遍所有的钞票。

先判断i-a[j]是否超界。(后面会用到)

我们可以从要凑成的钱数里减去5元再在所用的钞票数里加上1,用算式表达:f[i-a[j]]+1,还要再f[i]和它之间去小值(因为f[i]可能之前已经有值了)

最后判断f[s]是否为最大值(0x3f3f3f3f)如果是的话,说明凑不出来,输出-1,否则输出它的值。

程序结束。

程序:

#include<bits/stdc++.h>
using namespace std;
int s,n,f[100100]={0},a[60]={0};
int main()
{
#ifdef LOCAL
    freopen( "1.in", "r", stdin );
    freopen( "1.out", "w", stdout );
#endif
    scanf("%d%d",&s,&n);
    memset(f,0x3f3f3f3f,sizeof f);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        f[a[i]]=1;
    }
    f[0]=0;
    for(int i=1;i<=s;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i-a[j]>=0)
            {
                f[i]=min(f[i],f[i-a[j]]+1);
            }
        }
    }
    if(f[s]==0x3f3f3f3f) cout<<"-1";
    else cout<<f[s];
    return 0;
}

 

标签:组合,硬币,int,min,1961,钞票,freopen,0x3f3f3f3f
From: https://www.cnblogs.com/wjk53233/p/16790017.html

相关文章

  • 换硬币
    7-4换硬币分数7作者C课程组单位浙江大学将一笔零钱换成5分、2分和1分的硬币,要求每种硬币至少有一枚,有几种不同的换法?输入格式:输入在一行中给出待换的零钱数额x......
  • Java并发编程学习5-对象的组合
    对象的组合前面的博文,我们已经了解了关于线程安全和同步的一些基础知识。本篇博文将介绍一些线程安全的组合模式,来帮助我们确保使用这些模式开发的程序是线程安全的。1.......
  • 排列组合
    排列组合九大解题技巧(按理解难度排序)先选后排:先将元素选出来,再进行排列,非常有效的降低问题的复杂度。特殊优先:特殊元素,优先处理;特殊位置,优先考虑。分排用直排:$n$......
  • 多重组合数
    多重组合数是这样的一个柿子。\[\binom{n}{n_1,n_2\dotsn_t}=\frac{n!}{\prod\limits_{i=1}^tn_i!}\]意思就是一个可重集,每个相同的元素的个数集合是\(n\)集合的全排......
  • 回溯 组合问题(三)
    leetcode17题目描述:给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下(与电话按键相同)。注意1不对......
  • 回溯 组合问题(二)
    题目描述:leetcode216找出所有相加之和为 n的 k 个数的组合,且满足下列条件:只使用数字1到9每个数字 最多使用一次 返回所有可能的有效组合的列表。该列表不能......
  • ARC150D Removing Gacha(组合)
    ARC150DRemovingGacha有一棵\(N\)个白点的树根为\(1\),每次等概率随机选一个到\(1\)的路径上有白点的点涂黑,问期望几次整棵树被涂黑。模\(998244353\)。CODE首先......
  • Thread专题(3) - 组合对象
    此文被笔者收录在系列文章​​​架构师必备(系列)​​中虽然前面介绍了一些线程安全与同步的基础知识,但我们不希望为了获得线程安全而去分析每次内存访问,而希望组合成更大的......
  • 初识设计模式 - 组合模式
    简介组合模式就是组合多个对象形成树形结构以表示具有“部分-整体”关系的层次结构。组合模式对单个对象(叶子对象)和组合对象(容器对象)的使用具有一致性。组合模式的关键......
  • 回溯算法 组合问题(一)
    题目来自leetcode77题给定两个整数n和k,返回范围[1,n]中所有可能的k个数的组合。你可以按任何顺序返回答案。示例1:输入:n=4,k=2输出:[[2,4],[3,4],......