说实话我第一次在洛谷刷到 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 0dp[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 算法流程整个算法的执行顺序非常固定按下面几步走就不会乱读入 N, K以及 N 种奶酪的高度和营养值。读入 M以及被标记为大奶酪的种类编号。跑一遍普通完全背包得到dp[0..K]含义是“不触发塔顶大奶酪规则时的最大原价值”。用dp[K]初始化答案这对应塔顶不是大奶酪的情况。遍历每一种大奶酪把当前大奶酪作为塔顶计算v[id] dp[K - h[id]] / 2更新答案。输出答案。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; vectorint h(N 1), v(N 1); for (int i 1; i N; i) { cin h[i] v[i]; } int M; cin M; vectorint 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 个裕量防止边界溢出。如果你不确定数据范围可以拿vectorint 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 0dp[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价值 1K 1答案是 1。如果 K 2再给一种高度 1 价值 100 的小奶酪那么大奶酪塔顶 一个小奶酪在下塔顶价值 1下方价值 100/2 50总 51而不用大奶酪的纯小奶酪塔两块小奶酪价值 200。答案应该是 200这个例子能同时检验dp[K]初始化和整除逻辑。6. 常见问题速查表问题现象原因与处理输出答案比预期小只枚举了大奶酪塔顶没算无大奶酪方案答案初始化为dp[K]再和大奶酪方案比较数组越界大奶酪高度超过 KK - h[id]为负数枚举前判断h[id] K直接跳过答案多算或漏算 1减半写成四舍五入题目要求向下取整直接用整数除法/2大奶酪编号错乱多种奶酪时答案异常确认输入编号是 1-based数组从下标 1 开始存样例通过但部分点 WAdp数组含义理解成“恰好高度”本题是“不超过高度”dp[K]本身就是不超过 K 的最优值想给背包加状态转移越来越复杂停手改为枚举塔顶大奶酪塔身交给普通背包这张表基本覆盖了这道题所有常见报错点。如果你 WA 了先对照表排查前三行大概率能直接找到问题。7. 举一反三从 Cheese Towers 到三值排序7.1 USACO 题目的通用套路USACO 早期题目有一个很鲜明的特点基础算法不难但题目喜欢在规则上加一个“单点特殊判断”。比如另一道常见题 Sorting a Three-Valued Sequence中文常叫三值排序给一个只含 1、2、3 的序列允许交换任意两个位置的数求最少交换次数使序列有序。三值排序的常规做法是统计 1、2、3 各自应该出现的位置然后先处理“直接交换就能归位”的错位对再处理环形错位。它和你现在做的奶酪塔有个共同底层逻辑先把问题当成一个普通模型处理再把特殊规则单独拆出来。奶酪塔的普通模型是完全背包特殊规则是塔顶大奶酪三值排序的普通模型是“统计错位”特殊规则是“一次交换可以修复两个错位”。我甚至可以说USACO 白银组很多题都长这样第一眼看起来是某个经典算法第二眼发现规则里头藏着猫腻第三眼才意识到猫腻只出现在一个孤立的边界上。做题时养成“找边界”的习惯比多背十道模板题有用得多。7.2 这类“特殊规则 背包”怎么练如果你想把这类题吃透建议按这个顺序自问三个问题特殊规则作用在哪个位置奶酪塔里是塔顶三值排序里是“交换双方是否形成直接归位”。这个位置能不能枚举塔顶大奶酪种类只有 M 种交换对也只有有限种组合枚举代价通常很小。把这个位置固定住以后剩下部分还是不是一个经典问题奶酪塔剩下的塔身是普通背包三值排序剩下的是统计错位数量。三个问题都能回答思路基本就通了。如果三个问题里第二个回答不了说明规则作用的位置太多才需要考虑改状态设计如果能回答就老老实实枚举边界不要给自己加戏。我个人在实际做题中还有一个习惯遇到这种“有特殊条件的背包”我先把特殊条件全部删掉写一个最朴素的背包确保它能跑对然后单独写一个函数处理特殊条件最后合并答案。这个习惯让我少踩了无数坑也推荐给你。奶酪塔这题本身不难难的是你愿不愿意先把问题拆开再动手。
