HDU6685 Rikka with Coin

83 阅读 0 评论 55 点赞

我是靠谱客的博主自觉纸飞机，最近开发中收集的这篇文章主要介绍HDU6685 Rikka with Coin，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

http://acm.hdu.edu.cn/showproblem.php?pid=6685
题意：有无限面值为10，20，50，100的硬币。有n道菜，最少带多少枚硬币才能使得不管点哪道菜都足够支付且不找零。
思路：10的最多1个（10+10不如10+20），20的最多3个（20+20+20+20不如10+20+20+50），50的最多1个（50+50不如50+100），然后计算至少需要多少个100。暴力枚举 $2 * 4 * 2 = 16$ 种情况即可。

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
using namespace std;
const int M=100+10;
const int INF=0x3f3f3f3f;
int a[105];
int main()
{
    int T;
    scanf("%d",&T);
    bool ok[2][4][2][300]={0};
    for (int i=1;i>=0;i--)
    {
        for (int j=3;j>=0;j--)
        {
            for (int k=1;k>=0;k--)
            {
                for(int a1=i;a1>=0;a1--)for(int a2=j;a2>=0;a2--)for(int a3=k;a3>=0;a3--)ok[i][j][k][a1*10+a2*20+a3*50]=1;
            }
        }
    }
    while(T--)
    {
        int n;
        scanf("%d",&n);
        bool flag=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if (a[i]%10!=0) flag=1;
        }
        if (flag)
        {
            printf("-1n");
            continue;
        }
        int ans=INF;
        for (int i=0;i<=1;i++)
        {
            for (int j=0;j<=3;j++)
            {
                for (int k=0;k<=1;k++)
                {
                    int ret=0,sum=0;
                    for (int l=1;l<=n;l++)
                    {
                        if(a[l]>=100&&ok[i][j][k][a[l]%100+100])ret=(a[l]-a[l]%100-100)/100;
                        else if(ok[i][j][k][a[l]%100])ret=(a[l]-a[l]%100)/100;
                        else ret=(1<<30);
                        sum=max(sum,ret);
                    }
                    ans=min(ans,sum+i+j+k);
                }
            }
        }
        printf("%dn",ans);
    }
    return 0;
}