「PA 2020」Cukierki 题解

算法思路

本题使用动态规划和背包问题的变种来解决子集选择问题。核心思想是判断哪些子集能够表示从 $1$ 到子集和的所有数值。

关键观察

1. 问题转化

一个子集 $S$ 满足条件当且仅当：对于任意 $y \in [1, \sum S]$，都能用 $S$ 的某个子集表示出 $y$。

2. 充要条件

将糖果按重量排序后，子集 $S = \{a_1, a_2, \ldots, a_k\}$（已排序）满足条件当且仅当：

$$a_{i+1} \leq 1 + \sum_{j=1}^i a_j \quad \text{对于所有 } i $$

代码解析

排序预处理

sort(a + 1, a + n + 1);

将糖果按数量从小到大排序，这是满足条件的关键。

动态规划状态

ll f[maxn * maxn];  // f[j] 表示当前能表示[1,j]的所有子集方案数
f[0] = 1;  // 空集的方案数为1

动态规划转移

for (int i = 0; i < n; i++) {
    sum += a[i];
    
    for (int j = 5000; j >= a[i + 1] - 1; j--) {
        f[min(j + a[i + 1], 5000)] = (f[min(j + a[i + 1], 5000)] + f[j]) % mod;
    }
}

转移解释：

• 当前考虑第 $i+1$ 袋糖果
• 如果当前能表示区间 $[1, j]$，且 $a_{i+1} \leq j + 1$
• 那么加入 $a_{i+1}$ 后能表示区间 $[1, j + a_{i+1}]$
• 限制在 $5000$ 以内因为 $a_i \leq 5000$

答案统计

for (int i = 1; i <= 5000; i++)
    ans += f[i], ans %= mod;

统计所有非空子集的方案数。

算法正确性

条件验证

对于已排序的子集 $\{a_1, a_2, \ldots, a_k\}$：

• 初始能表示 $[0,0]$
• 加入 $a_1$ 后能表示 $[0, a_1]$，需要 $a_1 = 1$ 才能表示 $1$
• 加入 $a_2$ 时，如果 $a_2 \leq 1 + a_1$，则能表示 $[0, a_1 + a_2]$
• 依此类推，保证连续性

动态规划正确性

• $f[j]$ 记录当前能表示到 $j$ 的方案数
• 转移时确保新加入的糖果不会破坏连续性条件

复杂度分析

• 排序：$O(n \log n)$
• 动态规划：$O(n \cdot \text{maxSum}) = O(n \cdot 5000)$
• 总复杂度：$O(n \cdot 5000)$

关键技巧

1. 排序预处理：确保糖果按升序处理
2. 连续性检查：通过 $a_{i+1} \leq 1 + \text{当前和}$ 保证能表示所有数值
3. 滚动数组：使用一维数组优化空间
4. 模运算处理：正确处理大数取模