思路

题目的思维量很高，参考大佬的题解

1. 要想用的币最少，我们可以用贪心的思想，用的币值越大越好

2. 因为大的币值一定是小的币值的倍数，所以一个大的币值一定可以代替i个相等小的币值，所以我们可以用小的币值的更新大的币值。

3. 状态定义：f[i] 表示在使用面值最大为i合法硬币序列时，我们用的最少钱币数量

4. 状态转移，根据前面的分析可以得知，f[i] 可以用来更新大面值的结果，所以我们可以用f[i] 更新f[i * j] , f[i * j] = min(f[i * j], f[i] - cnt), cnt ： 使用面值i * j 之后可以减少的钱币数量。

5. cnt 的计算方法，每个兔子减少：

6. 最后取min(f[i])即可

7. 注意点当i * j > max_price 时无意义，为什么这么说呢，因为题目要求不能找零，所以大于max_price 的币花不出去。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 1e5 + 10;
int f[N], w[N];// f[i]表示在使用面值最大为i合法硬币序列时，我们用的最少钱币数量
int main()
{
    memset(f, 0x3f, sizeof f);
    f[1] = 0;
    int n, max_price = -1;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> w[i];
        f[1] += w[i];
        max_price = max(max_price, w[i]);
    }
    //cout << max_price << endl;
    for(int i = 1; i <= max_price; i ++)
    {
        for(int j = 2; i * j <= max_price; j ++)
        {
            int cnt = 0;
            for(int k = 1; k <= n; k ++)
            {
                cnt +=  w[k] / (i * j);
            }
            cnt = cnt * (j - 1);
            f[i * j] = min(f[i * j], f[i] - cnt);
        }
    }
    int res = 1e9 + 10;
    for(int i = 1; i <= max_price; i ++)
    {
        res = min(res, f[i]);
    }
    cout << res << endl;
    return 0;
}