传送门

题意是说有面值10 20 50 100的钱，有n个价格给定的菜，要求用最少的硬币数量，使得所有n个菜品的价格都能被凑出来。

贪心：直观想法是先用大的面值，依次用小的面值。

这样的话可以发现10， 20， 20， 50四个面值能凑出所有100以内的价格。

但是有个例外：90 110 这样的数据，如果按照上面的贪法是100 50 20 20 10五个硬币，实际上只需要50 20 20 20四个硬币就可以拼出来。

所以进一步发现用10 20 20 20 50五个硬币可以包含所有最优方案。两个10肯定能用一个20代替，四个20肯定能用一个50 20 10代替。

所以做一个10 20 20 20 50的子集生成。然后暴力判断dish[i] % 100 + 100和dish[i] % 100在某个组合的子集生成里有没有。（有先后顺序，第一个如果有了第二个就不用判断。因为既然零钱数量是固定的，那么100圆的越少约好）如果有，100圆的数量就分别是(dish[i] - （dish[i] % 100 + 100）/ 100) ，和dish[i] / 100。

对于100圆判断是个重要细节。
比如1000 90 110这样的数据，1000其中的100圆可以用零钱拼出来，所以100圆个数只有9个。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[5] = {10, 20, 20, 20, 50};
int b[10], n;
ll d[210];
set<int> st[1 << 6];
void dfs(set<int> &t, int now, int sum)
{
    t.insert(sum);
    //if(now > n) return;
    while(now < n)
    {
        ++now;
        dfs(t, now, sum + b[now]);
    }
}
int main()
{
    freopen("02.in", "r", stdin);
    for(int i = 1; i < 1 << 5; i++)
    {
        n = 0;
        for(int j = 0; j < 5; j++)
        {
            if(1 & (i >> j)) b[n++] = a[j];
        }
        n--;
        for(int j = 0; j <= n; j++) dfs(st[i], j, b[j]);
    }

    // for(int i = 1; i < 1 << 5; i++)
    // {
    //     cout << i << ':';
    //     for(auto it = st[i].begin(); it != st[i].end(); it++) cout << *it << ' ';
    //     cout << endl;
    // }
    int T; cin >> T;
    while(T--)
    {
        int num; scanf("%d", &num);
        int flag = 0;
        for(int i = 1; i <= num; i++) 
        {
            scanf("%lld", &d[i]);
            if(d[i] % 10) flag = 1;
        }
        //sort(d + 1, d + 1 + num);
        if(flag)
        {
            printf("-1\n");
            continue;
        }
        ll ans = 1e12;
        for(int i = 0; i < 1 << 5; i++)
        {
            if(i == 23)
            {
                int debug = 1;
            }
            int cz = __builtin_popcount(i);
            ll dol = 0;
            int can = 1;
            for(int j = 1; j <= num; j++)
            {
                if(d[j] >= 100)
                {
                    int tmp = d[j] % 100;
                    tmp += 100;
                    if(st[i].find(tmp) != st[i].end()) 
                    {
                        dol = max((d[j] - tmp) / 100, dol);
                        continue;
                    }
                }
                if(st[i].find(d[j] % 100) != st[i].end()) dol = max(d[j] / 100, dol);
                else if(d[j] % 100 == 0) dol = max(d[j] / 100, dol);
                else can = 0;  
            }
            if(can == 0) continue;
            //ans = min(ans, dol + cz);
            if(ans > dol + cz) ans = dol + cz;
        }
        cout << ans << endl;
    }
}
//23:10 20 30 40 50 60 70 80 90 100

// 110 70 190
// 1010 90 110