$\LARGE\color{orange}{刷题日记(算法提高课)}$

这道题题目的意思是，给定一个 $(n,\ a)$ ，求最小的 $m$ 使得 $(m,\ b)$ 与其等价

在这里「等价」的定义为：向量 $a[i]$ 可以表示的数，$b[i]$ 同样可以表示；对于不能表示的数也同理

我们从样例的角度出发来理解这个过程

$3,\ 19,\ 10,\ 6$

在这里面 6 和 19 都是重复的，因为 $6 = 3 + 3,\ 19 = 10 + 3 + 3 + 3$

因此这 4 个数用 2 个就可以替代，所以 $m=2$

也就是说，对于给定的一组数 $a[1\dots n]$ ，我们需要删去所有可以由其他数表示的数，即删去所有满足 $a_i=a_{i_1}+a_{i_2}+\dots +a_{i_k}$ 的 $a_i$

我们将 $a[0\dots n]$ 从小到大排序，然后考察每个数 $a[i]$ ，如果 $a[i]$ 可以用 $a[0\dots i-1]$ 之间的加和表示，那么我们就删去该数

问题转换后，我们每个数可以使用的此时是无限次，因此这是一个完全背包求方案数的问题，我们需要判断的是方案数是否为 0

完整代码：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110, M = 25000 + 10;

bool f[M];
int q[N];
int n;

int main()
{
    int k;
    cin >> k;
    while(k--)
    {
        cin >> n;
        for(int i = 1; i <= n; i++)
            cin >> q[i];

        memset(f, false, sizeof f);
        f[0] = true;

        sort(q + 1, q + 1 + n);
        int m = q[n];

        int cnt = 0;
        for(int i = 1; i <= n; i++)
        {
            if(!f[q[i]]) cnt++;//要先判断，之后再对数组进行赋值
            for(int j = q[i]; j <= m; j++)
                f[j] |= f[j - q[i]];
        }

        cout << cnt << endl;
    }
    return 0;
}

我们在判断何时让 $cnt$ 增加的时候，需要在对 $f[j]$ 赋值之前完成

这里我们回顾 $f[i][j]$ 的定义：对前 $i$ 个数考虑，加和恰好为 $j$ 的方案数

由于我们对空间进行了压缩，因此赋值前的 $f[j]$ 表示上一层的状态，赋值后表示当前层的状态

由于我们是看在 0 到 $i-1$ 当中有没有数能过凑出 $a[i]$ ，也就是我们应该去看上一层的状态，所以这里的判断不能写在循环的后面