[Ahoi2013]找硬币
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 348 Solved: 114
[Submit][Status]
Description
Input
Output
一行,一个整数,表示最少付的钱币数。
Sample Input
25 102
Sample Output
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]找硬币(搜索)的更多相关文章
-
【bzoj 3233】[Ahoi2013]找硬币 ——搜索
Description 小蛇是金融部部长.最近她决定制造一系列新的货币.假设她要制造的货币的面值为x1,x2,x3… 那么x1必须为1,xb必须为xa的正整数倍(b>a).例如 1,5,125, ...
-
BZOJ 3233: [Ahoi2013]找硬币( dp )
dp(x)表示最大面值为x时需要的最少硬币数. 枚举x的质因数p, dp(x) = min( dp(x/p) - (p-1) * sigma[a[i]/x] ). ----------------- ...
-
BZOJ 3233: [Ahoi2013]找硬币
BZOJ 3233: [Ahoi2013]找硬币 标签(空格分隔): OI-BZOJ OI-DP Time Limit: 10 Sec Memory Limit: 64 MB Description ...
-
[Bzoj3233][Ahoi2013]找硬币[基础DP]
3233: [Ahoi2013]找硬币 Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 924 Solved: 482[Submit][Status][ ...
-
BZOJ3233:[AHOI2013]找硬币(DP)
Description 小蛇是金融部部长.最近她决定制造一系列新的货币.假设她要制造的货币的面值为x1,x2,x3… 那么x1必须为1,xb必须为xa的正整数倍(b>a).例如 1,5,125, ...
-
【BZOJ 3233】 [Ahoi2013]找硬币
[题目 描述] 小蛇是金融部部长. 最近她决定制造一系列新的货币. 假设她要制造的货币 的面值为 x1, x2, x3… 那么 x1 必须为 1, xb 必须为 xa 的正整数倍(b>a). 例 ...
-
[bzoj3233] [Ahoi2013]找硬币
一开始没什么思路...后来想到确定最大硬币面值就知道其他面值能取多少了..而且结果是可以由较小的面值转移过来的. f[i]表示最大面值为i时的最小硬币数.a[i]表示第i个物品的价钱. f[i]=mi ...
-
【bzoj3233】【ahoi2013】找硬币
题意: 求确定n种货币面额x1..xn满足 x1=1 且xi为xj的整数倍(i>j) 给定n个物品价格ai 求使用上面货币最少需要硬币数(不能找零) 题解: 动态规划 听说网上的题解都是搜索的做 ...
-
BZOJ3233【AHOI2013】找硬币
题面 题解 最优肯定是尽可能用大面值硬币 设$f[i]$表示最小面值为$i$时的最小答案 则:(令$p$是$i$的最小质因子) $$ f[\frac ip]=min(f[\frac ip], f[i] ...
随机推荐
-
不要着急改代码,先想想--centos 6.8下编译安装tmux
诸位读者新年好,2017开年第一篇博客,请允许我先问候一下看到这篇博客的诸位.写博客是我2017年定下的目标之一,希望我会坚持下去. 最近打算尝试一下tmux这个神器,于是有了这一篇关于思维方式的Bl ...
-
Dedecms去掉URL中a目录的方法
本文实例讲述了Dedecms去掉URL中a目录的方法.分享给大家,供大家参考.具体分析如下: 使用dedecms的朋友可能会发现自己的URL目录生成是会自动带有一个/A/目录了,那么要如何去掉URL中 ...
-
Hive删除数据库
DROP DATABASE是删除所有的表并删除数据库的语句.它的语法如下: DROP DATABASE StatementDROP (DATABASE|SCHEMA) [IF EXISTS] data ...
-
iOS7.1 编译报错 解决方案 体会
iOS升级到 iOS 7.1 了 ,开发人员必须与时俱进.果断下载更新了xcode5.1版本 ,试运行了一下已上线的应用,哇 报错了!好头疼 贴下报错地方: 都是关于第三方类库报的错 比如parse. ...
-
[未完成]关于SQL语句的总结
关于SQL语句的总结关于SQL语句的总结关于SQL语句的总结关于SQL语句的总结关于SQL语句的总结
-
用Cookie和Session实现用户登录 函数
由于网页是一种无状态的连接程序,你无法得知用户的浏览状态,必须通过Cookie或Session记录用户的有关信息. Cookie: 是一种在远程浏览器端储存数据并以此来跟踪和识别用户的机制. PHP透 ...
-
sql server 2000 和 sql server 2005 数据库连接字符串区别
//sql server 2000 <add name="Connection" connectionString="Data Source=.;Initial C ...
-
Arcgis For Android之GPS定位实现
翻开曾经做的东西,看了看,非常多从逻辑上比較乱,对之做了改动,完毕后实现的效果为: MapActivity源码例如以下: package com.lzugis.map; import java.io. ...
-
C#串口通信程序详解
C#串口通信程序详解 摘要:创建C#串口通信程序需要注意什么呢?创建C#串口通信程序的步骤是什么?那么本文就向你详细介绍创建C#串口通信程序集体的内容. 在.NET平台下创建C#串口通信程序,.NET ...
-
gulp实现公共html代码复用
在开发网站的时候,尤其是类似于官网这样的项目,顶部都会有一个导航栏,底部会有一些其他信息,而这两个部分在每一个页面都是有的.我们不可能在每个html页面都写一遍,这样也不便后期维护等操作,所以可以把顶 ...