ECNU 3306. 有钱人买钻石（贪心+dfs）3306. 有钱人买钻石

86 阅读 0 评论 57 点赞

我是靠谱客的博主失眠荷花，最近开发中收集的这篇文章主要介绍ECNU 3306. 有钱人买钻石（贪心+dfs）3306. 有钱人买钻石，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

3306. 有钱人买钻石

题面统计数据讨论

单点时限: 2.0 sec

内存限制: 256 MB

有一个有钱人，他身上带了好多硬币。但是这么多硬币由不方便带，所以他决定要用这些硬币去买钻石。

有趣的是，店里只剩下一颗钻石了。这颗钻石的价格是 P。他身边由一元硬币 N1 枚，五元硬币 N2 枚，十元硬币 N3 枚，二十五元硬币 N4 枚。这些硬币都是一样重的。有钱人当然希望花的硬币越重越好，也就是说数量越多越好，但也不想让商家找钱。你知道应该怎么做吗？

输入格式

第一行一个整数 P，第二行用空格隔开的四个整数 N1,N2,N3,N4。(1≤P≤108,0≤N1,N2,N3,N4≤108)。

对于 30% 的数据，有 P≤103,0≤N1,N2,N3,N4≤100。

输出格式

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

样例

input

13
3 2 1 1

output

input

13
1 1 1 1

output

Impossible

题解：这个题目，乍一看以为是dp背包，可是数据量却那么大，只有1,5,10,25四种面额的硬币，每种数量若干，要使得能够刚好兑换成功总金额，在此前提下，还要使得硬币数量越多越好。我们当然是要让面额小的尽量多使用，但是如果面额小的使用某一值H时，后面可能就无法兑换成功，这时我们从H开始递减地去枚举使用量，但是数据量最大可为10^8，我们是不是要枚举全部值（10^8）呢？这样当然不行。你想，如果只有1和5两种面额的硬币，我们枚举面额1的硬币为high时，只需要枚举区间（high,high-5）,再接着去枚举5的硬币，如果这个区间的硬币都无法兑换成功，那就是不行的。

依次类推面额最大为25，我们枚举时只要枚举（high,high-25）这个区间即可。

代码如下：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=4;
int v[maxn],num[maxn];
int p,N1,N2,N3,N4;
void init()
{
v[0]=1;v[1]=5;v[2]=10;v[3]=25;
num[0]=N1;num[1]=N2;num[2]=N3;num[3]=N4;
}
int dfs(int coin,int sum,int ans)//目前兑换到第几种硬币、目前已兑换总额、已经使用的硬币数量
{
if(coin==4)
{
if(sum==p)
return ans;
if(sum!=p)
return -1;
}
if(sum==p)
return ans;
if(sum>p)
return -1;
int left=p-sum;
int tans=-1;
int high=min(left/v[coin],num[coin]);//目前此硬币最多可以用多少
int low=max(0,high-25);
for(int i=high;i>=low;i--)//依次枚举，枚举到成功则跳出
{
int tem=dfs(coin+1,sum+i*v[coin],ans+i);
if(tem!=-1)
{
tans=tem;
break;
}
}
return tans;
}
int main()
{
cin>>p>>N1>>N2>>N3>>N4;
init();
int res=dfs(0,0,0);
if(res==-1)
cout << "Impossiblen";
else
cout << res << endl;
return 0;
}