洛谷P8687题解

本题考虑使用状压 DP。

设糖果口味总数为 $m$，使用二进制数 $s \in {0, 1}^m$ 表示口味集合，其中第 $k$ 位为 $1$ 当且仅当该集合包含第 $k$ 种口味。

定义状态 $f(s)$ 为覆盖口味集合 $s$ 所需的最小糖果包数。初始条件为：

• $f(\emptyset) = 0$（空集不需要任何糖果包）

• $f(s) = +\infty$（对于所有非空集合 $s$）

状态转移方程：

对于每包糖果的口味集合 $a_i$（$1 \leq i \leq n$），遍历所有可能的状态 $s$，更新：

$$
f(s \cup a_i) = \min(f(s \cup a_i), f(s) + 1)
$$

可以得到如下代码：

memset(f, 0x3f3f3f3f, sizeof(f));
f[0] = 0;
for (int i = 0; i < n; i++) {
    for (int s = 0; s < 1 << m; s++) {
        if (f[s] > 105) continue;
        f[s | a[i]] = min(f[s | a[i]], f[s] + 1);
    }
}

完整代码就不给了，希望这篇题解对你有所帮助。