杭电2019多校第九场 HDU-6685 Rikka with Coin（思维+暴力）

142 阅读 0 评论 94 点赞

我是靠谱客的博主真实画板，这篇文章主要介绍杭电2019多校第九场 HDU-6685 Rikka with Coin（思维+暴力），现在分享给大家，希望可以做个参考。

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6685

题意：T组样例，每组样例会给出n个数，现在你有无穷多的10、20、50、100的硬币，问最少带多少硬币，可以这n个数都可以凑出来。如果不能输出-1。

思路：首先，如果不能整除10，肯定就是-1。比赛时，思路是分类讨论，零头也就是10、20、30、40、50、50+10、50+20、50+30、50+40，这9种情况。如果大于50，就像式子写的那样，用一个50，剩下的又变成了10、20、30、40。所以，最后零头也就有10、20、30、40、50，对这5种情况分类讨论。事实证明这种思路是错误的，比如20、40、60，只用3个20就行。如果按我的思路，要用1个10,2个20,1个50。然后，加了特判还是WA了。队友又给了一个样例150、190、210，这时，只要100/50/20/20/20。也就是说，存在不用50，而用之前有的凑。那这样，情况太多了，根本没法讨论。正如上面的样例，10最多有1个，20最多有3个（用3个20凑60，如果是80，用1个10，1个20,1个50显然更优，这样还能凑出10、20、30。），50最多有1个，100的个数要么是w[i]/100要么是w[i]/100-1,暴力检查即可。

复制代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,w[110];
bool check(int i1,int i2,int i5,int x)
{
	for(int i=0;i<=i1;i++)
		for(int j=0;j<=i2;j++)
			for(int k=0;k<=i5;k++)
				if(i*10+j*20+k*50==x)
					return 1;
	return 0;
}
int main(void)
{
	int t,i10,ans;
	bool can,no;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		ans=1e9,no=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&w[i]);
			if(w[i]%10) no=1;
		}
		if(no)
		{
			printf("-1n"); continue;	
		}	
		sort(w+1,w+1+n);
		n=unique(w+1,w+1+n)-(w+1);
		for(int i1=0;i1<=1;i1++)
			for(int i2=0;i2<=3;i2++)
				for(int i5=0;i5<=1;i5++)
				{
					i10=0,can=1;
					for(int i=1;i<=n;i++)
					{
						if(w[i]<100)
						{
							if(!check(i1,i2,i5,w[i]))	
								can=0;						
						}
						else if(check(i1,i2,i5,w[i]%100+100))
							i10=max(i10,w[i]/100-1);
						else if(check(i1,i2,i5,w[i]%100))
							i10=max(i10,w[i]/100);
						else
						{
							can=0;
							break;
						}
					}
					if(can) ans=min(ans,i1+i2+i5+i10);
				}
		printf("%dn",ans);
	}
	
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,w[110];
bool check(int i1,int i2,int i5,int x)
{
	for(int i=0;i<=i1;i++)
		for(int j=0;j<=i2;j++)
			for(int k=0;k<=i5;k++)
				if(i*10+j*20+k*50==x)
					return 1;
	return 0;
}
int main(void)
{
	int t,i10,ans;
	bool can,no;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		ans=1e9,no=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&w[i]);
			if(w[i]%10) no=1;
		}
		if(no)
		{
			printf("-1n"); continue;	
		}	
		sort(w+1,w+1+n);
		n=unique(w+1,w+1+n)-(w+1);
		for(int i1=0;i1<=1;i1++)
			for(int i2=0;i2<=3;i2++)
				for(int i5=0;i5<=1;i5++)
				{
					i10=0,can=1;
					for(int i=1;i<=n;i++)
					{
						if(w[i]<100)
						{
							if(!check(i1,i2,i5,w[i]))	
								can=0;						
						}
						else if(check(i1,i2,i5,w[i]%100+100))
							i10=max(i10,w[i]/100-1);
						else if(check(i1,i2,i5,w[i]%100))
							i10=max(i10,w[i]/100);
						else
						{
							can=0;
							break;
						}
					}
					if(can) ans=min(ans,i1+i2+i5+i10);
				}
		printf("%dn",ans);
	}
	
	return 0;
}