10721.调味平衡

markdown
复制
1# 调味平衡 题解
2
3## 题目分析
4
5题目给出 $n$ 种食材，第 $i$ 种食材的酸度为 $a_i$，甜度为 $b_i$。我们可以选择每种食材放或不放。总酸度 $A$ 为所选食材 $a_i$ 之和，总甜度 $B$ 为所选食材 $b_i$ 之和。调味平衡要求 $A = B$，目标是最大化 $A + B$。
6
7设 $S = A + B$，因为 $A = B$，所以 $S = 2A = 2B$，即我们在满足 $A = B$ 的前提下最大化 $A$ 或 $B$ 即可。
8
9若直接枚举子集，复杂度为 $O(2^n)$，$n$ 最大可达 $100$ 左右，显然不能接受，需要更高效的算法。
10
11## 解题思路
12
13我们将每种食材的选择看作一个物品。对于第 $i$ 种食材，若选择它，酸度增加 $a_i$，甜度增加 $b_i$。可以构造两个量：
14
15- **总价值**：$x_i = a_i + b_i$，表示选择该食材对总和 $A+B$ 的贡献。
16- **重量差值**：$y_i = a_i - b_i$，表示酸度与甜度的差值变化。
17
18那么问题转化为：从 $n$ 个物品中选出一个子集，使得总重量 $\sum y_i = 0$，同时最大化总价值 $\sum x_i$。这是一个典型的 **01背包问题**，只是物品的重量可能为正、负或零。
19
20## 算法说明
21
22### 状态设计
23
24令 `f[w]` 表示当前已选物品的总重量为 $w$ 时，能获得的最大总价值。由于 $y_i$ 的范围大约在 $[-C, C]$（根据代码中 $C=505$ 可推断出题目数据范围），总重量可能从 $-N \cdot C$ 到 $N \cdot C$。为了使用数组下标表示负值，我们加入一个偏移量 `BASE = N * C`，将实际重量 $w$ 映射到下标 `w + BASE`。于是 `f` 数组大小为 `D = 2 * N * C`。
25
26初始时：`f[BASE] = 0`，其余位置设为负无穷（表示不可达）。
27
28### 状态转移
29
30对于每个物品 `(x, y)`（其中 $x = a+b, y = a-b$），按照 01 背包的方式更新 `f` 数组：
31
32- 若当前总重量为 $w$，选择该物品后总重量变为 $w' = w + y$，总价值变为 $v' = f[w] + x$。
33- 我们需要用 $f[w]$ 去更新 $f[w']$：`f[w'] = max(f[w'], f[w] + x)`。
34
35为了保证每个物品只被使用一次，需要根据 $y$ 的正负确定遍历顺序：
36
37- **若 $y \le 0$**：$w' = w + y \le w$，即新状态的下标比原状态小。为了避免同一轮中重复使用该物品，应**正序**遍历 $w$（从小到大），这样更新时使用的是上一轮的值（相当于用旧状态更新新状态，且新状态不会在本轮被再次使用）。
38- **若 $y > 0$**：$w' = w + y > w$，新下标更大，应**倒序**遍历 $w$（从大到小），原理同上。
39
40代码中这一段处理得非常精巧：
41
42```cpp
43if (y <= 0) {
44    for (int i = -y; i < D; i++)
45        f[i + y] = max(f[i + y], f[i] + x);
46} else {
47    for (int i = D - y - 1; i >= 0; i--)
48        f[i + y] = max(f[i + y], f[i] + x);
49}

以 $y \le 0$ 为例：$-y$ 是非负数，从 $i = -y$ 开始遍历，保证了 $i + y \ge 0$，不会越界。这里 $i$ 相当于原重量下标，$i+y$ 是新重量下标。正序遍历 $i$，就等价于用旧的 $f[i]$ 去更新 $f[i+y]$，且 $i+y \le i$，不会在本轮重复更新。$y > 0$ 的情况完全对称。

答案获取

所有物品处理完后，总重量为 $0$ 的状态对应下标 BASE，因此答案为 f[BASE]。由于我们存储的是总价值 $x$ 的最大值，而 $x = a+b$，恰好就是题目要求的 $A+B$ 最大值，直接输出即可。

时间复杂度分析

• 物品数量 $n \le 100$。
• 状态数组大小 $D = 2 \times N \times C$，其中 $C \approx 500$，$D \approx 10^5$。
• 每个物品的处理需要遍历 $D$ 个位置，总复杂度为 $O(n \cdot D) \approx 100 \times 10^5 = 10^7$，在 1 秒时限内可以轻松通过。

空间复杂度为 $O(D)$，约 $10^5$ 个 int，完全满足 512MB 的内存限制。

参考代码及解释

下面是完整的 C++ 代码，已经包含详细注释。

cpp
复制
1#include <cstdio>
2#include <algorithm>
3using namespace std;
4
5const int N = 105;          // 最大食材种类
6const int C = 505;          // 单种食材酸度/甜度上限（经验值）
7const int D = N * C * 2;    // 偏移后数组大小
8
9int n;
10int f[D];                   // DP数组，f[w]表示重量为w时的最大价值和
11
12int main() {
13    scanf("%d", &n);
14    
15    // 初始化：只有重量0（对应下标BASE）可达，价值为0
16    const int BASE = N * C;
17    for (int i = 0; i < D; i++)
18        f[i] = -1e9;        // 负无穷表示不可达
19    f[BASE] = 0;
20    
21    while (n--) {
22        int a, b;
23        scanf("%d%d", &a, &b);
24        
25        int x = a + b;      // 总价值
26        int y = a - b;      // 重量差值
27        
28        // 根据y的正负决定遍历方向，保证01背包正确性
29        if (y <= 0) {
30            // y<=0时，新下标 <= 旧下标，正序遍历
31            for (int i = -y; i < D; i++)
32                f[i + y] = max(f[i + y], f[i] + x);
33        } else {
34            // y>0时，新下标 > 旧下标，倒序遍历
35            for (int i = D - y - 1; i >= 0; i--)
36                f[i + y] = max(f[i + y], f[i] + x);
37        }
38    }
39    
40    // 重量0对应的下标即为BASE，输出该状态的价值
41    printf("%d\n", f[BASE]);
42    
43    return 0;
44}

总结

这道题本质上是将“两种属性和相等”转化为“差值重量为0”的 01 背包问题。通过引入差值作为重量、和作为价值，并在 DP 数组上做偏移处理负下标，实现了高效求解。关键在于正确选择正序或倒序遍历，以保证每个物品最多选择一次。

此类“平衡型”最优化问题在信息学竞赛中经常出现，希望大家能掌握这个转化与偏移技巧，灵活应用到类似题目中。