hdu6685 Rikka with Coin【枚举】【思维】【2019 Multi-University Training Contest 9】

65 阅读 0 评论 43 点赞

我是靠谱客的博主健忘火龙果，最近开发中收集的这篇文章主要介绍hdu6685 Rikka with Coin【枚举】【思维】【2019 Multi-University Training Contest 9】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意:

你有10元硬币，20元硬币，50元硬币，100元硬币若干
现在有n个价格，请问最少带多少个硬币可以不用找钱能支付任意一个价格

题解：

首先10元的硬币最多只会用一个，如果用了两个，直接替换成一个10元、一个20元一定不亏。
20元的硬币最多只会用三个，如果用了四个，直接替换成一个10元、两个20元、一个50元一定不亏。
50元的硬币最多只会用一个，如果用了两个，直接替换成个50元和一个100元一定不亏。
对于任何一种情况，重复使用上述规则一定会达到一个10元硬币最多一个，20 元最多三个，50 元最多一个的情况，不会陷入重复甩锅的死循环。

然后对使用硬币的情况进行枚举,一共 2 * 4 * 2 = 16 种情况

对于每个价格，我们优先判断是否不小于100，然后我们再把其拆出 (%100后的部分) + 100 和若干个100进行组合,判断i个10和j个20和k个50能否组成 (%100后的部分) + 100，不能则再判断能否组成 (%100后的部分), 然后每次判断最多需要多少个100, 将16种情况枚举完取最小的答案。

AC_code:

#include<bits/stdc++.h>
#define inf 1e8
using namespace std;
bool ok[2][4][2][200];
int a[105];
void init() {
	memset(ok, false, sizeof(ok));
	for(int i = 0; i < 2; i ++) {
		for(int j = 0; j < 4; j++) {
			for(int k = 0; k < 2; k++) {
				for(int a1 = 0; a1 <= i; a1++) {
					for(int a2 = 0; a2 <= j; a2++) {
						for(int a3 = 0; a3 <= k; a3++) {
							ok[i][j][k][a1*10+a2*20+a3*50] = true;
						}
					}
				}
			}
		}
	}
}
int main() {
	init();
	int t, n;
	cin>>t;
	while(t--) {
		bool flag = true; 
		cin>>n;
		for(int i = 0; i < n; i++) {
			cin>>a[i];
			if(a[i] % 10 != 0){
				flag = false;
			}
		}
		if(!flag){
			puts("-1");
			continue;
		}
		int minn = inf;
		for(int i = 0; i < 2; i++) {
			for(int j = 0; j < 4; j++) {
				for(int k = 0; k < 2; k++) {
					int sum = 0, ret;
					for(int h = 0; h < n; h++) {
						if(a[h] >= 100 && ok[i][j][k][a[h]%100+100]) {
							ret = a[h] / 100 - 1;
						} else if(ok[i][j][k][a[h]%100]) {
							ret = a[h] / 100;
						} else {
							ret = inf;//无法组成 则给予一个很大的数字
						}
						sum = max(sum, ret);
					}
					minn = min(minn, sum + i+j+k);
				}
			}
		}
		cout<<minn<<endl;
	}
	return 0;
}