货币系统 【每日一题】5月27日

一.题目链接

货币系统

二.题目大意

给 n 种面值的硬币，每个硬币的面值为 a[i]，求最少用多少枚硬币能表示原先硬币能表示的所有面值.

三.分析

题目即求最多选出多少硬币可以被其他硬币表示，直接暴力求就行了，同时用 f[i] 表示面值为 i 的硬币能否被表示出来优化.

四.代码实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int M = (int)25000;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;

int a[M + 5];
bool f[M + 5];

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int T; scanf("%d", &T);
    while(T--)
    {
        int n; scanf("%d", &n);
        for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        sort(a + 1, a + n + 1);
        memset(f, 0, sizeof(f));
        int cnt = 1;
        for(int i = 1; i * a[1] <= a[n]; ++i) f[i * a[1]] = 1;
        for(int i = 2; i <= n; ++i)
        {
            if(f[a[i]]) continue;
            ++cnt, f[a[i]] = 1;
            for(int j = a[i] + 1; j <= a[n]; ++j) if(!f[j] && f[j - a[i]]) f[j] = 1;
        }
        printf("%d\n", cnt);
    }
    return 0;
}