AcWing 532. 货币系统

题目传送门

一、题目解析

感觉这道题重点不是 \(DP\) 而是证明……很多高赞题解都是直接上结论的……，学习算法，个人感觉还是把理论基础打牢才靠谱

比如你考场的时候，想到了这个解法，如果用了怕结论是错的，得分还不如部分分；不用又怕错失正解，其实是很纠结的……所以我这里就写一写证明过程吧，其实也不难。

Statement

有 \(n\) 种不同面值的货币，第 \(i\) 种面值为 \(a[i]\) ，每种无限张。

将一个有 \(n\) 种货币、面值数组为 \(a[1…n]\) 的货币系统记作 \((n,a)\) 。两个货币系统 \((n,a)\),\((m,b)\) 等价：当且仅当对于任意 \(x∈N\) ，要么均能被两个货币系统表示出来，要么不能被任何一个表示。

给定一个货币系统 \((n,a)\) ，现在网友们打算简化一下货币系统,找到一个最小的 \(m\) 使得存在货币系统 \((m,b)\) 与 \((n,a)\) 等价。

\(n≤100\),\(a[i]≤25000\).

Thoughts & Solution

大写的简化啊！！明显在提示我们可以只简化，不用考虑替换成其它的货币金额啊！！！问题转化的能力是考查的重点，如果只是简化，那么简单：

（1）将货币面额排序（因为给的面额是无序的）

（2）每一个面额考查它能不能被它之前的面额描述出来，如果能，它就没有存在的必要。

当且仅当一张货币面额可以被该系统下其他货币表示时，此货币对该系统能表示的面额没有影响，换言之这个货币没有存在的必要，所以将这类的货币从系统中去除就可以得到等价的最小数量货币系统。

可以用\(dp\)求出能表示该面额的方案数，若对于一张货币方案数唯一（即只能被自己表示），则这张货币不能被省略，反之可以被省略，最后统计一下就行了。

#include 

using namespace std;
const int N = 110;      //N个正整数
const int M = 25010;    //表示的最大金额上限
int n;                  //实际输入的正整数个数
int v[N];               //每个输入的数字,也相当于占用的体积是多大
int f[M];               //二维优化为一维的DP数组，f[i]：面额为i时的前序货币组成方案数

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; i++)cin >> v[i];
        //每个货币的金额，都只能由比它小的货币组装而成，需要排一下序
        sort(v, v + n);
        //背包容量
        int m = v[n - 1];
        //每轮初始化一次dp数组，因为有多轮
        memset(f, 0, sizeof f);
        //在总金额是0的情况下，只有一种方案
        f[0] = 1;

        //利用01背包计算每个体积（面额）的组成方案
        for (int i = 0; i < n; i++)
            for (int j = v[i]; j <= m; j++)
                f[j] += f[j - v[i]];

        //统计结果数
        int res = 0;
        for (int i = 0; i < n; i++)
            //如果当前面额的组成方案只有一种，那么它只能被用自己描述自己，不能让其它人描述自己
            //这个面额就必须保留
            if (f[v[i]] == 1)res++;
        //输出结果
        printf("%d\n", res);
    }
}