说实话，我第一次在洛谷刷到 P2979 这个题号时，内心是有点不屑的。Cheese Towers，奶酪塔，USACO 2010 年 1 月的银组题，看起来不就是个完全背包吗？无限供应、高度上限、最大价值，这三件套凑一块，直接一层for循环套另一层for循环不就结束了。结果我 WA 了三次才意识到，这题真正的难点根本不在背包，而在题面角落里那句“如果塔顶是一块大奶酪，塔里其他奶酪的营养价值都要减半”。

这题适合两类人认真看：一是刚学完完全背包、想找点实战题练手的新手，二是已经会背包但总在“特殊规则”上翻车的老选手。它最有价值的地方，是逼你把一个看似要改背包状态的规则，拆成一次简单的枚举。今天我就把这题的完整拆解、代码、以及我踩过的几个坑，一次说清楚。

1. 先弄懂这题到底让你干什么

1.1 一句话拆解题面

题目描述相当直白：你有 N 种奶酪，第 i 种奶酪的高度是 h_i，营养值是 v_i，每种奶酪的数量无限。现在要搭一座总高度不超过 K 的奶酪塔，求塔的总营养值最大能到多少。到这里就是一个非常典型的完全背包问题，模板题中的模板题。

但题面接着补了一条规则：有 M 种奶酪被标记为“大奶酪”。如果某块大奶酪被放在整座塔的塔顶，那么塔里其他所有奶酪的营养值全部减半。注意关键词：塔顶、其他所有。这句话包含两个信息，第一，减半的对象不包括塔顶那块大奶酪本身；第二，只要塔顶大奶酪存在，下面不管堆多少层、用了什么奶酪，全部一视同仁减半。

如果不仔细想，很容易把这条规则理解成“大奶酪自带减半光环”，然后试图在背包状态里加一维去记录“塔里有没有放过减半大奶酪”。这个思路会在实现时把自己绕晕，因为同一块大奶酪，放在塔顶和放在塔底，效果完全不一样。问题的核心就在这个“塔顶”位置上。

1.2 为什么说它是“披着背包外衣的思维题”

完全背包本身没有任何新意，真正的新意在于：塔顶这个位置有且只有一个，它是全局唯一的边界。任何规则只要作用在唯一的位置上，我们就有一个非常自然的处理思路——枚举这个位置上放什么。

你可能会问：那我把大奶酪放在塔顶，下面的奶酪减半，会不会影响下面那一截的背包状态？会，但它影响的是“价值数值”，而不是“结构选择”。我可以先把塔从中间砍一刀：塔顶一块大奶酪，下面是剩下的部分。下面这一截无论怎么选，所有价值都会打五折，那我当然要让“打五折前的总价值”尽量大。于是这个问题就被拆成了两层：

• 塔顶：枚举每块大奶酪，价值单独按原值计算。
• 塔身：一个不包含任何特殊规则、纯普通完全背包，高度限制是 K 减去塔顶大奶酪的高度。

这个“砍一刀”的想法，是我花了三次 WA 才想明白的。很多人一开始的思路是修改背包内部的转移逻辑，比如在dp里额外开一维表示“有没有触发减半”，结果你会发现状态互相污染，因为塔顶大奶酪下面的所有奶酪减半，但你不知道塔顶会在哪个高度被放上去。枚举塔顶，本质上是在回避这个信息缺失问题。

2. 完全背包不是难点，但细节是

2.1 无限供应和高度限制如何映射到背包

既然每种奶酪无限供应，这就是标准完全背包。高度 K 就是背包容量，奶酪高度 h_i 是物品体积，营养值 v_i 是物品价值。每种奶酪可以取任意多块，所以内层循环必须从小到大正向遍历，这样才能让同一块奶酪被多次使用。

用生活化的例子说，你面前有几种不同厚度的书，每种书都有无限本，每本书的“知识量”不同，书包最多能装 K 厘米厚，问最多能装多少知识量。这不就是完全背包吗？每种书取多少本不受限制，只受总厚度约束。

这里还有一个容易被忽略的地方：题目要求“总高度不超过K”，不是“恰好等于 K”。很多背包模板题是“恰好装满”的，需要把dp数组初始化为负无穷，最后输出dp[K]。但本题不是，dp数组初始化为 0 即可，因为我不在乎是否刚好用完 K 的高度，能塞多少塞多少，塞不满也算合法方案。

2.2 转移方程和 dp 数组的真实含义

设dp[j]表示：在没有任何“塔顶大奶酪减半”规则的前提下，用所有种类的奶酪搭一座高度不超过 j 的塔，能获得的最大营养值。

转移方程是经典的完全背包：

for (int i = 1; i <= N; i++) { for (int j = h[i]; j <= K; j++) { dp[j] = max(dp[j], dp[j - h[i]] + v[i]); } }

外层枚举奶酪种类，内层正序枚举高度。dp[j - h[i]] + v[i]的意思是：先搭一座高度不超过 j - h[i] 的塔，再在最上面放一块第 i 种奶酪。注意我这里说的是“最上面”，因为在完全背包的转移里，每块新物品都相当于在当前组合的顶部追加一块，所以最终任意合法方案都能被表示出来。

关于dp[j]的“不超过”含义，可以这样理解：因为所有物品价值都是非负的，所以如果某高度塞不满，最优解也不会出现“为了用满高度而硬塞一个低价值奶酪”的情况。dp[j]天然就是容量不超过 j 时的最优答案。这也是为什么最后输出dp[K]而不是遍历dp[0..K]取最大值的原因——dp[K]本身就已经是“不超过 K”的最优值了。

2.3 容量 K 还是不超过 K：一个容易想歪的点

有人会把dp[j]理解成“恰好高度为 j”，然后思考：如果最优方案的总高度不到 K，那dp[K]是不是就不对了？不会。因为在正向转移中，dp[j]可以从dp[j - h[i]]转移过来，而后者已经是一个“不超过 j - h[i]”的值，所以dp[j]表示“不超过 j”的最优值。如果你实在不放心，可以把所有dp数组做一次前缀最大值：

for (int j = 1; j <= K; j++) dp[j] = max(dp[j], dp[j - 1]);

做不做这一步，本题答案都不变，因为高度越大的背包天然拥有更多选择空间，dp已经单调不降。但想清楚这一点，能避免你在枚举剩余高度时下意识犯下“必须刚好填满”的错误。

3. 大奶酪规则：把塔切成两截

3.1 规则只作用在“塔顶”这个位置

现在处理题目真正的难点。大奶酪规则说的是：如果塔顶是一块大奶酪，那么其他奶酪的营养值全部减半。这句话反过来读就是：只要塔顶不是大奶酪，那么塔里任何位置出现大奶酪，都只是普通奶酪，不会触发任何减半效果。

这给了我一个非常重要的分类依据。所有合法方案可以被分成两类：

• 第一类：塔顶不是大奶酪。此时所有奶酪按原价值计算，答案就是上面那个普通完全背包的dp[K]。
• 第二类：塔顶是一块大奶酪。此时塔顶大奶酪按原价值计算，塔身所有奶酪按一半价值计算。

第二类方案的塔顶大奶酪种类是可枚举的，因为总共只有 M 种大奶酪。那么问题就变成了：对于每一种大奶酪 i，如果我把它放在塔顶，塔身还能用多高的空间？

答案很简单：如果大奶酪 i 的高度是 h_i，那么塔身高度上限是 K - h_i。塔身部分的原最大价值是dp[K - h_i]，减半后就是dp[K - h_i] / 2。所以这类方案的答案就是：

v_i + dp[K - h_i] / 2

对所有大奶酪 i 取最大值，再和第一类的dp[K]比较，取较大者。这里有一个很关键的前提：塔身部分用的是普通完全背包的 dp 数组，不是带任何减半标志的数组。因为塔身部分处在塔顶大奶酪下面，它没有自己的“塔顶大奶酪”，所以它内部的奶酪即使有大奶酪，也只算普通砖块，价值规则和普通完全背包完全一致。

3.2 枚举塔顶大奶酪，剩下交给普通背包

枚举的过程简单到让人怀疑：这不是 O(NK) 的背包外面又套了一层 O(M) 吗？对，就是 O(M) 的额外开销，因为枚举的是奶酪种类，不是高度。伪代码如下：

int ans = dp[K]; // 第一类：塔顶不是大奶酪 for (int id : bigCheeseList) { if (h[id] > K) continue; // 高度超了，无法当塔顶 int remain = K - h[id]; ans = max(ans, v[id] + dp[remain] / 2); }

有人会问：那如果塔顶大奶酪很高，h[id] 等于 K 呢？此时remain = 0，dp[0] = 0，答案是v[id]，表示这座塔只有一块大奶酪，下面什么都没有。没有“其他奶酪”，自然没有奶酪被减半，完全合理。

还有另一个更隐蔽的问题：如果第二类的塔身部分里面，又选了一块大奶酪并处在这个塔身的顶部，那这块大奶酪会不会再次触发“塔顶减半”？

不会，因为整个塔的塔顶是最上面那块，塔身内部的大奶酪在物理位置上位于塔顶大奶酪的下面，它不是整座塔的塔顶，不满足题目规则的触发条件。我最初就是在这里绕晕的，总担心塔身内部也会递归地触发减半，然后试图设计一个二维状态去记录“塔身顶部是不是大奶酪”。实际上题目规则只以整座塔的塔顶为判断依据，和塔身内部结构无关。

3.3 为什么减半后还能直接用 dp[remain] / 2

这一步需要一点数学直觉。设dp[remain]是塔身高度不超过 remain 时的最大原价值。我要的是“原价值经过减半后的最大值”，也就是max(v(T) / 2)，其中 T 遍历所有高度不超过 remain 的合法方案。

因为函数f(x) = x / 2在整数域上是单调不减的，所以如果方案 A 的原价值大于等于方案 B 的原价值，那么 A 减半后的价值也大于等于 B 减半后的价值。于是：

max(v(T) / 2) = (max(v(T))) / 2 = dp[remain] / 2

这里除法是整数除法，向下取整，正好符合 USACO 对“减半”的定义。这个单调性极其重要，因为如果减半操作不是均匀乘一个系数，而是类似“高价值部分减半、低价值部分不减”的阶梯式规则，那我们就不能这么偷懒了。本题能这样做，完全是因为减半是线性的、单调的。

这也是整道题最漂亮的地方：你不需要额外创建一个“减半世界”的背包，只要普通背包算一遍，然后在外层枚举大奶酪，套一个/2就行。整个思路干净利落。

4. 完整代码与实现细节

4.1 算法流程

整个算法的执行顺序非常固定，按下面几步走就不会乱：

1. 读入 N, K，以及 N 种奶酪的高度和营养值。
2. 读入 M，以及被标记为大奶酪的种类编号。
3. 跑一遍普通完全背包，得到dp[0..K]，含义是“不触发塔顶大奶酪规则时的最大原价值”。
4. 用dp[K]初始化答案，这对应塔顶不是大奶酪的情况。
5. 遍历每一种大奶酪，把当前大奶酪作为塔顶，计算v[id] + dp[K - h[id]] / 2，更新答案。
6. 输出答案。

4.2 C++ 参考实现

#include <bits/stdc++.h> using namespace std; const int MAXK = 10005; int dp[MAXK]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, K; cin >> N >> K; vector<int> h(N + 1), v(N + 1); for (int i = 1; i <= N; i++) { cin >> h[i] >> v[i]; } int M; cin >> M; vector<int> big; for (int i = 0; i < M; i++) { int id; cin >> id; // 题目给的编号是 1-based big.push_back(id); } // 普通完全背包：所有奶酪都按原价值参与，不触发减半规则 memset(dp, 0, sizeof(dp)); for (int i = 1; i <= N; i++) { for (int j = h[i]; j <= K; j++) { dp[j] = max(dp[j], dp[j - h[i]] + v[i]); } } // 情况一：塔顶不是大奶酪 int ans = dp[K]; // 情况二：枚举每块大奶酪放在塔顶 for (int id : big) { if (h[id] > K) continue; // 单块高度已经超过限制，不能当塔顶 int remain = K - h[id]; ans = max(ans, v[id] + dp[remain] / 2); } cout << ans << '\n'; return 0; }

这个代码在洛谷 P2979 上可以直接 AC。dp数组开 10005 是因为原题里 K 的上限是 10000，开大 5 个裕量防止边界溢出。如果你不确定数据范围，可以拿vector<int> dp(K + 1)动态分配，更稳妥。

4.3 复杂度与边界条件

普通完全背包的时间复杂度是 O(NK)，空间复杂度 O(K)。枚举大奶酪的复杂度是 O(M)，M 最多不超过 N，所以整体复杂度仍然是 O(NK)。对原题 N ≤ 100、K ≤ 10000 的数据范围来说，一百万次运算在任意评测机上都是瞬间完成，完全不需要优化。

需要留意的边界条件有这几个：

• M可能等于 0，此时big数组为空，枚举循环直接跳过，答案就是dp[K]。虽然原题大概率不会给出空的大奶酪列表，但代码要能处理。
• 某块大奶酪高度超过 K，它无法成为整座塔的塔顶，因为总高度会超限。但注意，它仍然可以出现在普通背包中作为非塔顶奶酪，由于价值非负，普通背包会自然决定要不要用它。
• dp[0]在完全背包中默认是 0，表示空塔高度为 0 时价值为 0。枚举塔顶大奶酪时，如果remain = 0，dp[0] / 2 = 0，公式退化为单块大奶酪方案，这是对的。

4.4 一个容易被忽略的实现细节

如果你在枚举大奶酪时写成dp[remain]而不是dp[K - h[id]]，注意remain必须是非负的。当h[id] > K时，K - h[id]为负数，访问dp数组会产生未定义行为。所以代码里一定要先判断高度超限再计算剩余高度。

还有一个和整数除法有关的细节：C++ 里dp[remain] / 2对非负数就是向下取整。有的同学担心如果dp[remain]是奇数，向下取整会不会错？不会，题目要求的减半本身就是向下取整，是语义正确，不是精度损失。

5. 实战踩坑：我在这里 WA 了三次

5.1 坑一：把大奶酪标记带进了 dp 数组

我第一次做这道题时，想着既然塔顶大奶酪会让下面的奶酪减半，那我不如开一个二维状态dp[j][0/1]，0表示塔顶不是大奶酪，1表示塔顶是大奶酪。结果越写越乱，因为当塔顶是大奶酪时，塔身内部所有奶酪都要减半，但我不知道塔身内部的高度分配，无法在转移时确定当前奶酪是不是“位于塔顶奶酪下方”。

后来我想明白了，这个二维状态混淆了两个不同层次的问题：塔顶大奶酪的枚举是一个整体决策，而塔身内部的选择是一个独立子问题。把整体决策放进状态里，相当于把枚举复杂度从 O(M) 提高到了 O(K)，还要处理一堆状态合并规则，纯属自我折磨。正确做法是先跑一个纯净的普通背包，再从外面枚举塔顶。

5.2 坑二：忘记比较dp[K]这个无大奶酪塔顶的情况

有一次我改成了“枚举塔顶大奶酪”的思路，把所有大奶酪都枚举了一遍，输出答案。结果样例过了，提交却 WA 了一部分数据。原因是我只算了“塔顶是大奶酪”的情况，完全忘了还有一种可能：塔顶根本不放任何大奶酪。此时所有奶酪原汁原味，价值就是dp[K]。

更隐蔽的是，某些数据里最优解恰好是“塔顶不是大奶酪”的方案，因为塔顶大奶酪虽然自己价值高，但下面整截都要减半，反而可能不如普通方案。这类方案如果不单独用dp[K]初始化答案，就会被漏掉。记住：答案的初始值一定是dp[K]，而不是 0。

5.3 坑三：M 和编号从 1 开始

题目输入的大奶酪种类编号是 1-based，也就是对应输入奶酪的第几种。我第二次写的时候把编号当作下标直接用了，比如读入id后写h[id]、v[id]，但我的数组是从下标 0 开始存储的，于是第一块奶酪的下标是 1，第二块是 2，刚好错位。这个错误在只有一块奶酪的测试点上完全测不出来，等数据里有多种奶酪时就会随机爆炸。

解决办法有两个，要么把奶酪数组开成N + 1，下标从 1 开始存，输入的时候cin >> h[i] >> v[i]，其中i从 1 循环到 N；要么在读取大奶酪编号后减一，转成 0-based 下标。我建议用第一种，读起来更符合题目描述，也不容易出错。

5.4 坑四：对拍时发现整除方向问题

我和一个朋友对拍时，他写的是(dp[remain] + 1) / 2，也就是四舍五入的减半。我俩答案在小数据上经常差 1。查了原题才发现，USACO 官方对“halved”的处理是整数除法向下取整，也就是dp[remain] / 2。这里不要凭直觉做四舍五入，直接整除就对了。

如果你在本地测试，也可以构造一组简单数据验证：假设只有一种大奶酪，高度 1，价值 1，K = 1，答案是 1。如果 K = 2，再给一种高度 1 价值 100 的小奶酪，那么大奶酪塔顶 + 一个小奶酪在下：塔顶价值 1，下方价值 100/2 = 50，总 51；而不用大奶酪的纯小奶酪塔：两块小奶酪，价值 200。答案应该是 200，这个例子能同时检验dp[K]初始化和整除逻辑。

6. 常见问题速查表

这张表基本覆盖了这道题所有常见报错点。如果你 WA 了，先对照表排查前三行，大概率能直接找到问题。

7. 举一反三：从 Cheese Towers 到三值排序

7.1 USACO 题目的通用套路

USACO 早期题目有一个很鲜明的特点：基础算法不难，但题目喜欢在规则上加一个“单点特殊判断”。比如另一道常见题 Sorting a Three-Valued Sequence，中文常叫三值排序，给一个只含 1、2、3 的序列，允许交换任意两个位置的数，求最少交换次数使序列有序。

三值排序的常规做法是统计 1、2、3 各自应该出现的位置，然后先处理“直接交换就能归位”的错位对，再处理环形错位。它和你现在做的奶酪塔有个共同底层逻辑：先把问题当成一个普通模型处理，再把特殊规则单独拆出来。奶酪塔的普通模型是完全背包，特殊规则是塔顶大奶酪；三值排序的普通模型是“统计错位”，特殊规则是“一次交换可以修复两个错位”。

我甚至可以说，USACO 白银组很多题都长这样：第一眼看起来是某个经典算法，第二眼发现规则里头藏着猫腻，第三眼才意识到猫腻只出现在一个孤立的边界上。做题时养成“找边界”的习惯，比多背十道模板题有用得多。

7.2 这类“特殊规则 + 背包”怎么练

如果你想把这类题吃透，建议按这个顺序自问三个问题：

1. 特殊规则作用在哪个位置？奶酪塔里是塔顶，三值排序里是“交换双方是否形成直接归位”。
2. 这个位置能不能枚举？塔顶大奶酪种类只有 M 种，交换对也只有有限种组合，枚举代价通常很小。
3. 把这个位置固定住以后，剩下部分还是不是一个经典问题？奶酪塔剩下的塔身是普通背包，三值排序剩下的是统计错位数量。

三个问题都能回答，思路基本就通了。如果三个问题里第二个回答不了，说明规则作用的位置太多，才需要考虑改状态设计；如果能回答，就老老实实枚举边界，不要给自己加戏。

我个人在实际做题中还有一个习惯：遇到这种“有特殊条件的背包”，我先把特殊条件全部删掉，写一个最朴素的背包，确保它能跑对；然后单独写一个函数处理特殊条件，最后合并答案。这个习惯让我少踩了无数坑，也推荐给你。奶酪塔这题本身不难，难的是你愿不愿意先把问题拆开再动手。