<h1 id="heading">题目</h1>
<p>{% fold 点击显/隐题目 %}</p>
<div class="oj"><div class="part" title="Description"> 
有一个有钱人，他身上带了好多硬币。但是这么多硬币由不方便带，所以他决定要用这些硬币去买钻石。
有趣的是，店里只剩下一颗钻石了。这颗钻石的价格是 $P$。他身边由一元硬币 $N_1$ 枚，五元硬币 $N_2$ 枚，十元硬币 $N_3$ 枚，二十五元硬币 $N_4$ 枚。这些硬币都是一样重的。有钱人当然希望花的硬币越重越好，也就是说**数量**越多越好，但也**不想让商家找钱**。你知道应该怎么做吗？
</div><div class="part" title="Input">
第一行一个整数 $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$。
</div><div class="part" title="Output">
如果办不到，输出 <code>Impossible</code>，否则输出最多能花掉多少枚硬币。
</div><div class="samp"><div class="clear"></div><div class="input part" title="Sample Input">
13
3 2 1 1
<p>13<br>
1 1 1 1</p>
</div><div class="output part" title="Sample Output">
5
<p>Impossible</p>
</div><div class="clear"></div></div></div>
{% endfold %}

<h1 id="heading-1">题解</h1>
<p>一开始想复杂了<br>
尽可能用1元买,不够的时候用5元的买<br>
这里需要注意5个1元等于1个5元,也即<strong>如果把5个1元换成1个5元都没法完成目的,那么我再减少1元的数目没有意义</strong></p>
<p>这样就能发现,for几乎循环不了几次</p>
<h1 id="heading-2">代码</h1>
<p>{% fold 点击显/隐代码 %}```cpp 有钱人买钻石 <a href="https://github.com/OhYee/sourcecode/tree/master/ACM">https://github.com/OhYee/sourcecode/tree/master/ACM</a> 代码备份<br>
#include <algorithm><br>
#include <cstdio><br>
#include <iostream><br>
#include <vector><br>
using namespace std;</p>
<p>#define Log(format, ...) // printf(format, ##<strong>VA_ARGS</strong>)</p>
<p>const int maxn = 4;<br>
const int m[maxn] = {1, 5, 10, 25};<br>
int p;<br>
int a[maxn];</p>
<p>int dfs(int coin, int sum, int ans) {<br>
Log(&quot;%d %d %d\n&quot;, coin, sum, ans);<br>
if (sum == p) // 找到答案<br>
return ans;<br>
if (sum &gt; p) // 超过要求了<br>
return -1;</p>
<pre><code>int target = p - sum; //距离目标还差多少

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

// long long allchoose = sum;
// for (int i = coin; i &lt; maxn; ++i)
//     allchoose += m[i] * a[i];
// if (allchoose &lt; 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 &gt;= End; --i) {
    int tans2 = dfs(coin + 1, sum + i * m[coin], ans + i);
    if (tans2 != -1) {
        tans = tans2;
        break;
    }
}
return tans;
</code></pre>
<p>}</p>
<p>int main() {<br>
while (~scanf(&quot;%d&quot;, &amp;p)) {<br>
for (int i = 0; i &lt; maxn; ++i)<br>
scanf(&quot;%d&quot;, &amp;a[i]);</p>
<pre><code>    int ans = dfs(0, 0, 0);
    if (ans == -1)
        printf(&quot;Impossible\n&quot;);
    else
        printf(&quot;%d\n&quot;, ans);
}
return 0;
</code></pre>
<p>}</p>
<pre style="background-color:#fff">{% endfold %}</pre>

ecnu 3306.有钱人买钻石