[AHOI2013]找硬币(搜索)

时间:2022-08-31 19:26:51

[Ahoi2013]找硬币

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 348  Solved: 114
[Submit][Status]

Description

小蛇是金融部部长。最近她决定制造一系列新的货币。假设她要制造的货币的面值为x1,x2,x3… 那么x1必须为1,xb必须为xa的正整数倍(b>a)。例如1,5,125,250就是一组合法的硬币序列,而1,5,100,125就不是。不知从哪一天开始,可爱的蛇爱上了一种萌物——兔纸!从此,小蛇便走上了遇上兔纸娃娃就买的不归路。某天,小蛇看到了N只可爱的兔纸,假设这N 只兔纸的价钱分别是a1,a2…aN。现在小蛇想知道,在哪一组合法的硬币序列下,买这N只兔纸所需要的硬币数最少。买兔纸时不能找零。
 
 
 

Input

第一行,一个整数N,表示兔纸的个数
第二行,N个用空格隔开的整数,分别为N只兔纸的价钱
 
 
 

Output

一行,一个整数,表示最少付的钱币数。

 
 
 

Sample Input

2
25 102

Sample Output

4

HINT

样例解释:共有两只兔纸,价钱分别为25和102。现在小蛇构造1,25,100这样一组硬币序列,那么付第一只兔纸只需要一个面值为25的硬币,第二只兔纸需要一个面值为100的硬币和两个面值为1的硬币,总共两只兔纸需要付4个硬币。这也是所有方案中最少所需要付的硬币数。

1<=N<=50, 1<=ai<=100,000

Source

分析:鉴于N很小,又面值确定后答案就确定了(因为肯定是先拿大面值的搞,剩余的再小面值的搞,所以这种贪心是一定的),故可以搜索,但是这个搜索里剪枝比较奇葩……具体请看http://www.cppblog.com/MatoNo1/archive/2013/06/17/200747.html

[AHOI2013]找硬币(搜索)的更多相关文章

  1. 【bzoj 3233】&lbrack;Ahoi2013&rsqb;找硬币 ——搜索

    Description 小蛇是金融部部长.最近她决定制造一系列新的货币.假设她要制造的货币的面值为x1,x2,x3… 那么x1必须为1,xb必须为xa的正整数倍(b>a).例如 1,5,125, ...

  2. BZOJ 3233&colon; &lbrack;Ahoi2013&rsqb;找硬币&lpar; dp &rpar;

    dp(x)表示最大面值为x时需要的最少硬币数. 枚举x的质因数p,  dp(x) = min( dp(x/p) - (p-1) * sigma[a[i]/x] ). ----------------- ...

  3. BZOJ 3233&colon; &lbrack;Ahoi2013&rsqb;找硬币

    BZOJ 3233: [Ahoi2013]找硬币 标签(空格分隔): OI-BZOJ OI-DP Time Limit: 10 Sec Memory Limit: 64 MB Description ...

  4. &lbrack;Bzoj3233&rsqb;&lbrack;Ahoi2013&rsqb;找硬币&lbrack;基础DP&rsqb;

    3233: [Ahoi2013]找硬币 Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 924  Solved: 482[Submit][Status][ ...

  5. BZOJ3233&colon;&lbrack;AHOI2013&rsqb;找硬币&lpar;DP&rpar;

    Description 小蛇是金融部部长.最近她决定制造一系列新的货币.假设她要制造的货币的面值为x1,x2,x3… 那么x1必须为1,xb必须为xa的正整数倍(b>a).例如 1,5,125, ...

  6. 【BZOJ 3233】 &lbrack;Ahoi2013&rsqb;找硬币

    [题目 描述] 小蛇是金融部部长. 最近她决定制造一系列新的货币. 假设她要制造的货币 的面值为 x1, x2, x3… 那么 x1 必须为 1, xb 必须为 xa 的正整数倍(b>a). 例 ...

  7. &lbrack;bzoj3233&rsqb; &lbrack;Ahoi2013&rsqb;找硬币

    一开始没什么思路...后来想到确定最大硬币面值就知道其他面值能取多少了..而且结果是可以由较小的面值转移过来的. f[i]表示最大面值为i时的最小硬币数.a[i]表示第i个物品的价钱. f[i]=mi ...

  8. 【bzoj3233】【ahoi2013】找硬币

    题意: 求确定n种货币面额x1..xn满足 x1=1 且xi为xj的整数倍(i>j) 给定n个物品价格ai 求使用上面货币最少需要硬币数(不能找零) 题解: 动态规划 听说网上的题解都是搜索的做 ...

  9. BZOJ3233【AHOI2013】找硬币

    题面 题解 最优肯定是尽可能用大面值硬币 设$f[i]$表示最小面值为$i$时的最小答案 则:(令$p$是$i$的最小质因子) $$ f[\frac ip]=min(f[\frac ip], f[i] ...

随机推荐

  1. 不要着急改代码,先想想--centos 6&period;8下编译安装tmux

    诸位读者新年好,2017开年第一篇博客,请允许我先问候一下看到这篇博客的诸位.写博客是我2017年定下的目标之一,希望我会坚持下去. 最近打算尝试一下tmux这个神器,于是有了这一篇关于思维方式的Bl ...

  2. Dedecms去掉URL中a目录的方法

    本文实例讲述了Dedecms去掉URL中a目录的方法.分享给大家,供大家参考.具体分析如下: 使用dedecms的朋友可能会发现自己的URL目录生成是会自动带有一个/A/目录了,那么要如何去掉URL中 ...

  3. Hive删除数据库

    DROP DATABASE是删除所有的表并删除数据库的语句.它的语法如下: DROP DATABASE StatementDROP (DATABASE|SCHEMA) [IF EXISTS] data ...

  4. iOS7&period;1 编译报错 解决方案 体会

    iOS升级到 iOS 7.1 了 ,开发人员必须与时俱进.果断下载更新了xcode5.1版本 ,试运行了一下已上线的应用,哇 报错了!好头疼 贴下报错地方: 都是关于第三方类库报的错 比如parse. ...

  5. &lbrack;未完成&rsqb;关于SQL语句的总结

    关于SQL语句的总结关于SQL语句的总结关于SQL语句的总结关于SQL语句的总结关于SQL语句的总结

  6. 用Cookie和Session实现用户登录 函数

    由于网页是一种无状态的连接程序,你无法得知用户的浏览状态,必须通过Cookie或Session记录用户的有关信息. Cookie: 是一种在远程浏览器端储存数据并以此来跟踪和识别用户的机制. PHP透 ...

  7. sql server 2000 和 sql server 2005 数据库连接字符串区别

    //sql server 2000 <add name="Connection" connectionString="Data Source=.;Initial C ...

  8. Arcgis For Android之GPS定位实现

    翻开曾经做的东西,看了看,非常多从逻辑上比較乱,对之做了改动,完毕后实现的效果为: MapActivity源码例如以下: package com.lzugis.map; import java.io. ...

  9. C&num;串口通信程序详解

    C#串口通信程序详解 摘要:创建C#串口通信程序需要注意什么呢?创建C#串口通信程序的步骤是什么?那么本文就向你详细介绍创建C#串口通信程序集体的内容. 在.NET平台下创建C#串口通信程序,.NET ...

  10. gulp实现公共html代码复用

    在开发网站的时候,尤其是类似于官网这样的项目,顶部都会有一个导航栏,底部会有一些其他信息,而这两个部分在每一个页面都是有的.我们不可能在每个html页面都写一遍,这样也不便后期维护等操作,所以可以把顶 ...