题目

{% fold 点击显/隐题目 %}

有一个有钱人，他身上带了好多硬币。但是这么多硬币由不方便带，所以他决定要用这些硬币去买钻石。 有趣的是，店里只剩下一颗钻石了。这颗钻石的价格是 $P$。他身边由一元硬币 $N_1$ 枚，五元硬币 $N_2$ 枚，十元硬币 $N_3$ 枚，二十五元硬币 $N_4$ 枚。这些硬币都是一样重的。有钱人当然希望花的硬币越重越好，也就是说**数量**越多越好，但也**不想让商家找钱**。你知道应该怎么做吗？
第一行一个整数 $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

{% endfold %}

题解

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

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

代码

{% fold 点击显/隐代码 %}```cpp 有钱人买钻石 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
#include
#include
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;

}

{% endfold %}