首页 > > 程序设计 > C/C++ >

Too Rich HDU - 5527 （贪心+dfs）

2018-09-01 05:37:57来源：博客园阅读 ()

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

Input

The first line contains an integer

Output

For each test case, please output the maximum number of coins and/or banknotes he can pay for exactly

Sample Input

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

-1

Source

2015ACM/ICPC亚洲区长春站-重现赛（感谢东北师大）

题意：给你一些不同面值的硬币，每种硬币都有一定的数量，求用尽可能多的硬币凑出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;
}