有钱人买钻石

ECNU-3306

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

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<string>

#include<cmath>

#include<map>

#include<vector>

#include<unordered_map>

#include<bitset>

using namespace std;

int value[4];

int num[4];

int p,n1,n2,n3,n4;

/**

 * coin表示现在进行到第几个硬币，sum表示已经凑到的和，ans表示使用的数量

 */

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 maxs=min(left/value[coin],num[coin]);

	int mins=max(0,maxs-25);

	int temp=-1;

	for(int i=maxs;i>=mins;i--){

		int now=dfs(coin+1,sum+i*value[coin],ans+i);

		if(now!=-1){

			temp=now;

			break;

		}

	}

	return temp;

}

int main(){

	cin>>p>>num[0]>>num[1]>>num[2]>>num[3];

	value[0]=1,value[1]=5,value[2]=10,value[3]=25;

	int ans=dfs(0,0,0);

	if(ans==-1){

		cout<<"Impossible"<<endl;

	}else{

		cout<<ans<<endl;

	}

}

巴特西

有钱人买钻石+dfs中使用贪心

有钱人买钻石

ECNU-3306

最新文章

热门文章