这是一篇最后编辑于 8 年前 的文章，其内容可能与目前实际情况差异较大，请注意甄别
题目
{% 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，否则输出最多能花掉多少枚硬币。
题解
一开始想复杂了
尽可能用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 %}