【2019杭电多校训练赛】HDU6685 / 1006-Rikka with Coin 题解

• 题意
• 解题思路

题目来自于：HDU6685 Rikka with Coin

题意

题目的大意是给你10，20，50，100四种硬币，你最少要带多少个硬币才能吃到其中的任一道菜并且没有找零。

解题思路

这题有一个极限贪心的思想，我们知道会出现以下情况：

• 只能出现两个10元硬币，因为10，10，10的情况必然可以换成10，20
• 只能出现三个20元硬币，因为20，20，20，20的情况必然可以换成10，20，50
• 只能出现一个50元硬币，因为50，50的情况必然可以换成100

这样我们就可以用穷举法来写这道题目。

#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <algorithm>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
const ll mod=998244353;
const int maxn=1e6+100;

int a[200];

int jud(int i10,int i20,int i50,int num) {
	for(int i=0; i<=i10; i++) {
		for(int j=0; j<=i20; j++) {
			for(int k=0; k<=i50; k++) {
				if(i*10+j*20+k*50==num)return 1;
			}
		}
	}
	return 0;
}

int main() {
//    freopen("in1.txt","r",stdin);
//    freopen("out.txt","w",stdout);
	int t;
	scanf("%d",&t);
	while(t--) {
		int n,flag=0;
		scanf("%d",&n);
		for(int i=1; i<=n; i++) {
			scanf("%d",&a[i]);
			if(a[i]%10!=0)flag=1;
		}
		if(flag==1) {
			printf("-1\n");
			continue;
		}
		int minans=INF;
		for(int i=0; i<=1; i++) { //10
			for(int j=0; j<=3; j++) { //20
				for(int k=0; k<=1; k++) { //50
					int cnt=0;
					int ans=-1;
					for(int l=1; l<=n; l++) {
						int s=a[l]/100;
						if(a[l]%100==0 && a[l]>=100 && jud(i,j,k,100)==1) {
							s--;
						} else if(a[l]%100==10 && a[l]>100 && jud(i,j,k,110)==1) {
							s--;
						} else if(jud(i,j,k,a[l]%100)==0)break;
						cnt=l;
						ans=max(ans,s+i+j+k);
					}
					if(cnt==n) {
						minans=min(minans,ans);
					}
				}
			}
		}
		printf("%d\n",minans);
	}
	return 0;
}