Too Rich HDU - 5527 (贪心+dfs)
卢比奥十佳球,碧昂斯经典歌曲,海南英才网
too rich
time limit: 6000/3000 ms (java/others) memory limit: 262144/262144 k (java/others)
total submission(s): 1850 accepted submission(s): 480
problem description
you are a rich person, and you think your wallet is too heavy and full now. so you want to give me some money by buying a lovely pusheen sticker which costs pdollars from me. to make your wallet lighter, you decide to pay exactly p dollars by as many coins and/or banknotes as possible.
for example, if p=17 and you have two $10 coins, four $5 coins, and eight $1 coins, you will pay it by two $5 coins and seven $1 coins. but this task is incredibly hard since you are too rich and the sticker is too expensive and pusheen is too lovely, please write a program to calculate the best solution.
input
the first line contains an integer t indicating the total number of test cases. each test case is a line with 11 integers p,c1,c5,c10,c20,c50,c100,c200,c500,c1000,c2000, specifying the price of the pusheen sticker, and the number of coins and banknotes in each denomination. the number ci means how many coins/banknotes in denominations of i dollars in your wallet.
1≤t≤20000
0≤p≤109
0≤ci≤100000
output
for each test case, please output the maximum number of coins and/or banknotes he can pay for exactly p dollars in a line. if you cannot pay for exactly p dollars, please simply output '-1'.
sample input
3
17 8 4 2 0 0 0 0 0 0 0
100 99 0 0 0 0 0 0 0 0 0
2015 9 8 7 6 5 4 3 2 1 0
sample output
source
题意:给你一些不同面值的硬币,每种硬币都有一定的数量,求用尽可能多的硬币凑出p元钱,有可能凑不出
。
思路:首先按贪心的思想,用尽可能多的小面值钱币,前提是小面值钱币可以凑出当前需要的钱数,所以从大面值的开始决策,比如现在到第idx个面值的钱币,要凑x元,又用1~idx-1的钱币可以凑出的总金额为y元,那么当前面值我需要用(x - y) / c[i]个,当然如果这个值小于0,就不用当前面值的钱币,注意如果c[i]不能整除(x- y),则需要多用一个idx的钱币,因为剩下的钱不够,比如有 10 20 20 50 50,现在要凑110,110 - 10 - 20 - 20 = 60,50不能整除60,则就需要两个50的,因为只用一个50的话,剩下的凑不出60,还有一点要注意的是20不能整除50,200不能整除500,因此我们算个数的时候有时需要多加一个,比如20 20 20 50,现在要凑50,因为剩下3个20,一共可以凑60,按照贪心策略那个单独的50就不会被选了,因此这里需要强制选一个50,200和500同理
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
#define eps 1e-10
#define pi acos(-1.0)
#define ll long long
int const maxn = 1e5+7;
const int mod = 1e9 + 7;
int gcd(int a, int b) {
if (b == 0) return a; return gcd(b, a % b);
}
int p,ans,c[11];
int val[11]={0,1,5,10,20,50,100,200,500,1000,2000};
ll sum[11];
void dfs(int rest,int idx,int cnt)
{
if(rest<0)
return;
if(idx==0)
{
if(rest==0)
ans=max(ans,cnt);
return;
}
ll cur = max(rest-sum[idx-1],(ll)0);
int curnum=cur/val[idx];
if(cur % val[idx])
curnum++;
if(curnum<=c[idx])
dfs(rest-curnum*val[idx],idx-1,cnt+curnum);
curnum++;
if(curnum<=c[idx])
dfs(rest-curnum*val[idx],idx-1,cnt+curnum);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(sum,0,sizeof(sum));
ans=-1;
scanf("%d",&p);
for(int i=1;i<=10;i++)
scanf("%d",&c[i]);
for(int i=1;i<=10;i++)
sum[i]=sum[i-1]+(ll)(val[i]*c[i]);
dfs(p,10,0);
printf("%d\n",ans);
}
return 0;
}
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!!
点击进行留言回复
相关文章:
-
-
C++ 作用域
作用域:名称在翻译单元(包括文件)的可见范围 局部: 只在定义它的代码块中可用,如自动变量 全局(文件作用域): 从定义位置到文件结尾都可用 注意: 静...
[阅读全文]
-
-
-
-
聚合类型与POD类型
Lippman在《深度探索C++对象模型》的前言中写道: I have heard a number of people over the years ...
[阅读全文]
-
-
-
-
-
网友评论