[COCI 2008/2009 #2] PERKET

形式化题目

有 $n$ 种配料，第 $i$ 种带两个属性：酸度 $s_i$ 与苦度 $b_i$ 。选取任意非空子集 $S$ ，总酸度等于被选配料酸度的乘积，总苦度等于被选配料苦度的和。求所有非空选择中

|\prod_{i \in S} s_i - \sum_{i \in S} b_i|

的最小值。

思路

朴素想法就是枚举所有非空配料子集，而枚举本身就是最终做法： $n \leqslant 10$ 时非空子集最多 $2^{10} - 1 = 1023$ 个，没有任何需要优化的瓶颈。

关键观察有两点：

没有贪心规则：酸度是乘积、苦度是和，合并方式不对称。加入一种 $s = 1$ 的配料酸度不变、苦度却增加，所以"选谁、选几个"没有单调规律可循，只能枚举。
空集必须排除：全不选时乘积为 1、和为 0，会把答案带偏，必须保证至少选一种。

把每种配料看成 01 序列的一层：choose[i] = 1 表示选第 $i$ 种配料。dfs(dep) 只负责决定第 dep 层的取值；一条完整序列生成后（dep == n + 1）在叶子统一调用 check()——先确认非空，再按定义计算总酸度与总苦度并更新答案。这正是 rbook《01 序列枚举》文章的标准模型。

以样例 2 为例（配料 $(3,8)$ 、 $(5,8)$ ），所有非空选择如下：

选中的配料	choose 序列	总酸度（积）	总苦度（和）	差值
{1}	1 0	3	8	5
{2}	0 1	5	8	3
{1,2}	1 1	15	16	1
空集	0 0	1	0	（不合法，跳过）

行表示一条完整 01 序列对应的选择，列分别是酸度乘积、苦度和与差值。观察最后一行：全 0 序列如果不排除就会以差值 1 混入答案，这正是叶子 check() 必须做的事；三行合法选择中最小值是 1，与样例输出一致。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-13 13:21
 * update_at: 2026-08-13 13:21
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

int n;
int s[MAXN], b[MAXN]; // 第 i 种配料的酸度与苦度
int choose[MAXN];     // choose[i] = 1 表示选第 i 种配料
int ans = 2e9;        // |总酸度 - 总苦度| 的最小值

// 叶子节点：检查当前完整 choose[1..n] 是否合法，并更新答案。
void check() {
    int sour = 1;   // 总酸度是乘积，初值为 1
    int bitter = 0; // 总苦度是求和，初值为 0
    int cnt = 0;    // 统计选了几种配料

    for (int i = 1; i <= n; i++) {
        if (choose[i] == 1) {
            cnt++;
            sour *= s[i];
            bitter += b[i];
        }
    }

    if (cnt == 0) // 至少选一种配料，全不选的情况直接跳过
        return;

    int diff = abs(sour - bitter);
    if (diff < ans)
        ans = diff;
}

// dfs(dep) 枚举第 dep 种配料选不选，生成完整 01 选择序列。
void dfs(int dep) {
    if (dep == n + 1) { // 一条完整 01 序列已经生成
        check();
        return;
    }

    choose[dep] = 0; // 不选第 dep 种配料
    dfs(dep + 1);
    choose[dep] = 1; // 选第 dep 种配料
    dfs(dep + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i] >> b[i];
    }

    dfs(1); // 从第 1 种配料开始枚举

    cout << ans << endl;
    return 0;
}

复杂度

时间： $O(n \cdot 2^n)$ 。共 $2^n$ 条 01 序列，每个叶子扫描 $n$ 种配料计算； $n \leqslant 10$ 时约一万次操作。
空间： $O(n)$ 。三个数组加递归栈，递归深度最多 $n$ 。

总结

本题是"小规模子集枚举"的模板题：两个属性一个求积一个求和，合并方式不同，因此不存在贪心捷径， $n \leqslant 10$ 时直接枚举全部非空子集就是标准答案。01 序列递归写法的要点是"每层只做一个选/不选的决定，完整序列生成后在叶子统一检查合法性与答案"，即 rbook《01 序列枚举》的核心套路；把空集排除这一特例做好，代码就完整了。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16输入 n 种配料 (s_i, b_i)，n <= 10
        |
        v
01 序列枚举（main.cpp）
  choose[i] = 0/1 表示第 i 种配料选不选
  dfs(dep) 只决定 choose[dep]，递归生成全部 2^n 条序列
        |
        v
叶子节点统一检查 check()
  统计选中个数：cnt == 0（空集）跳过
  总酸度 = 选中 s 的乘积（初值 1）
  总苦度 = 选中 b 的和（初值 0）
  用 |总酸度 - 总苦度| 更新最小值 ans
        |
        v
输出 ans     复杂度 O(n * 2^n)，空间 O(n)

图中中间一段是核心：dfs 只负责"生成完整选择"，检查与统计全部推迟到叶子，这正是 01 序列枚举的教学结构。由于没有可优化的瓶颈，从输入到答案是一条直线，唯一的注意点（排除空集、乘积初值为 1）都发生在叶子 check() 里。