hdu6685 Rikka with Coin

题目链接

大意：给你一系列的数字，让你用若干个10,20,50,100的某个组合，可以组合出任意一个数字

思路：
$xyq$xyq聚聚说这个是签到题，但是自闭一场我都不会做，呜呜呜
分析一下，给你数字若个位数非零则显然无解。

然后对有解的情况进行判断一下：
我们来枚举10 20 50分别使用多少个。
题解如下：

然后就暴力判断是否可行，然后整百的部分直接用1美元代替即可

细节见代码：

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
int t,n,a[N];
int need;
int c(int A,int B,int C){
    vector<int>x;
    for(int i=1;i<=A;i++)x.pb(10);
    for(int i=1;i<=B;i++)x.pb(20);
    for(int i=1;i<=C;i++)x.pb(50);    
    for(int i=1;i<=n;i++){
        int sta=0;
        int can=1e9;
        for(int j=0;j<(1ll<<(A+B+C));j++){
            int res=0;
            for(int k=0;k<A+B+C;k++){
                if((1<<k)&j)res+=x[k];
            }
            if(res%100==a[i]%100||res==a[i]){
                sta=1;              
                can=min(can,(a[i]-res)/100);
            }
        }
        if(!sta)return 0;

        need=max(need,can);
    }
    return 1;
}
int main(){
    ios::sync_with_stdio(false);
    for(cin>>t;t;t--){
        cin>>n;
        int ans=0;
        for(int i=1;i<=n;i++)cin>>a[i];
        int sta=0;
        for(int i=1;i<=n;i++){
            if(a[i]%10){
                sta=1;
                break;
            }
        }
        int res=2e9;
        if(sta)cout<<-1<<endl;
        else{
            for(int i=0;i<=1;i++){
                for(int j=0;j<=3;j++){
                    for(int k=0;k<=1;k++){
                        need=0;
                        if(c(i,j,k)){
                            res=min(res,need+i+j+k);
                        }
                    }
                }
            }
            cout<<res<<endl;
        }
    }  
    return 0;
}