ecnu 3306.有钱人买钻石

294


题目


点击显/隐题目

有一个有钱人,他身上带了好多硬币。但是这么多硬币由不方便带,所以他决定要用这些硬币去买钻石。
有趣的是,店里只剩下一颗钻石了。这颗钻石的价格是 $P$。他身边由一元硬币 $N1$ 枚,五元硬币 $N2$ 枚,十元硬币 $N3$ 枚,二十五元硬币 $N4$ 枚。这些硬币都是一样重的。有钱人当然希望花的硬币越重越好,也就是说数量越多越好,但也不想让商家找钱。你知道应该怎么做吗?


第一行一个整数 $P$,第二行用空格隔开的四个整数 $N_1, N_2, N_3, N_4$。$(1 leq P leq 10^8, 0 leq N_1, N_2, N_3, N_4 leq 10^8)$。
对于 $30%$ 的数据,有 $P leq 10^3, 0 leq N_1, N_2, N_3, N_4 leq 100$。


如果办不到,输出 Impossible,否则输出最多能花掉多少枚硬币。


13
3 2 1 1

13
1 1 1 1



5

Impossible




题解


一开始想复杂了
尽可能用1元买,不够的时候用5元的买
这里需要注意5个1元等于1个5元,也即如果把5个1元换成1个5元都没法完成目的,那么我再减少1元的数目没有意义

这样就能发现,for几乎循环不了几次

代码


点击显/隐代码
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

#define Log(format, ...) // printf(format, ##__VA_ARGS__)

const int maxn = 4;
const int m[maxn] = {1, 5, 10, 25};
int p;
int a[maxn];

int dfs(int coin, int sum, int ans) {
    Log("%d %d %d\n", coin, sum, ans);
    if (sum == p) // 找到答案
        return ans;
    if (sum > p) // 超过要求了
        return -1;

    int target = p - sum; //距离目标还差多少

    if (coin == maxn - 1) { // 已经遍历到最后一种硬币
        int num = target / m[coin];
        if (target % m[coin] == 0 && num <= a[coin])
            return ans + num;
        else
            return -1;
    }

    // long long allchoose = sum;
    // for (int i = coin; i < maxn; ++i)
    //     allchoose += m[i] * a[i];
    // if (allchoose < p) // 剩下的全加上也达不到要求
    //     return -1;

    // 往后遍历
    int tans = -1;
    int Begin = min(target / m[coin], a[coin]);
    int End = max(0, Begin - 30);
    for (int i = Begin; i >= End; --i) {
        int tans2 = dfs(coin + 1, sum + i * m[coin], ans + i);
        if (tans2 != -1) {
            tans = tans2;
            break;
        }
    }
    return tans;
}

int main() {
    while (~scanf("%d", &p)) {
        for (int i = 0; i < maxn; ++i)
            scanf("%d", &a[i]);

        int ans = dfs(0, 0, 0);
        if (ans == -1)
            printf("Impossible\n");
        else
            printf("%d\n", ans);
    }
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论