今天打卡的是 USACO 2010 年 1 月银牌组的 P2979 Cheese Towers。这题在洛谷上叫 [USACO10JAN] Cheese Towers S翻译过来就是“奶酪塔”。题目本身不算难但那个“一旦塔的总高度达到或超过 K塔顶奶酪的美味值就要减半”的规则把一大票习惯直接套完全背包模板的人拦在了门外。我第一版用 C 写的朴素 DP 也理所当然地 WA 了后来把状态重新划分成“全价段”和“半价段”两个完全背包才把问题理清楚。这篇就把完整思路、踩坑过程和一版能直接 AC 的 C 实现都拆开讲适合正在刷 USACO、洛谷蓝题或者备战 CSP/NOIP 的信奥选手参考。1. 这道题到底在说什么无限取奶酪超过 K 就半价1.1 “超过 K 就半价”到底是怎么个半价法先还原一下原题大意。你有 N 种奶酪第 i 种奶酪的高度是 h[i]美味值是 v[i]。每种奶酪可以拿任意多个。你要堆一座奶酪塔要求总高度不超过 T目标是让总美味值尽量大。特殊规则在这里如果整座塔的总高度达到了 K那么从塔顶往下看从“第一块让累计高度达到或超过 K 的奶酪”开始一直到塔顶这些奶酪的美味值全部减半向下取整。也就是说触发点这块奶酪本身也要减半它下面的奶酪保持原价。这个规则特别容易读歪。很多人以为“只要整座塔高度超过 K就把所有奶酪都减半”或者“只把超过 K 的部分减半”这两种理解都不对。举个小例子就清楚了假设 K10你从下往上依次放了高度 4、4、4、4 的四块奶酪。放完前两块累计高度是 8没触发放第三块时累计高度变成 12第一次达到并超过 K所以第三块和第四块奶酪减半前两块保持原价。关键点在“第一块”也就是从底部往上数累计高度第一次跨过阈值的那块奶酪。它把整座塔天然切成了两段下面一段全部原价触发点和上面一段全部半价。1.2 为什么这个规则能卡住一大票完全背包选手如果只是普通的完全背包状态转移非常单纯dp[h] 表示高度恰好为 h 时能拿到的最大美味值每加入一块奶酪直接在上一个状态上叠加价值和高度就行。但 Cheese Towers 引入了一个“全局高度条件”。一块奶酪到底算原价还是半价不取决于它本身而取决于它被放在塔的哪个位置以及它放下去之后整座塔累计高度是否跨过了 K。这意味着你不能在跑背包的过程中简单地用一个 dp[h] 表示“高度为 h 的最优价值”因为同一个高度 h可能对应两种完全不同的情况这个高度 h 整座塔都没触发过 K所有奶酪原价这个高度 h 已经触发过 K塔里一部分奶酪原价、一部分半价。两种情况的“价值状态”不能混在一个数组里。这就是为什么第一眼看上去能套完全背包实际写出来却怎么都不对的原因。很多选手卡在这题不是不会完全背包而是没有意识到“触发阈值”这种全局条件需要额外做状态划分。2. 先别急着套完全背包朴素思路会在这里翻车2.1 完全背包的标准姿势价值与高度的单调递推先把常规完全背包写出来垫个底。定义 f[h] 表示高度恰好为 h 时在不考虑任何减半规则的情况下能拿到的最大原价美味值。转移就是标准的完全背包for (int h 1; h T; h) { for (int i 0; i N; i) { if (h h[i]) { f[h] max(f[h], f[h - h[i]] v[i]); } } }初始状态 f[0] 0其他为 0 或负无穷都行因为高度必须是正数跑出来 f[h] 如果还是 0 就表示无法恰好堆到这个高度。这个转移是单调的因为奶酪高度和美味值都是正的堆得越高通常价值越大但注意不是严格单调存在“堆不到某个高度”的情况。把这套东西直接搬到本题你会发现一个问题f[h] 默认所有奶酪都按照原价 v[i] 计入但实际塔高一旦达到 K有一部分奶酪只能按 v[i]/2 计入。也就是说f[h] 在 h 比较大的时候会虚高算出来的答案根本不是真实可用的方案。2.2 错误做法一把超过 K 的部分全部统一打五折有一种很自然的错误做法是先按原价跑完全背包得到 f[T]然后如果 T 超过 K就简单地认为“超过 K 的那部分高度对应的价值减半”于是答案写成 f[K-1] (f[T] - f[K-1]) / 2。这个做法在数学上就说不通。f[T] 里高度 K 之前堆的奶酪和高度 K 之后堆的奶酪并不是两段独立的最优解。你不能保证“前 K-1 高度价值最大化”和“后 T-K1 高度价值最大化”能够无缝拼接成同一座合法塔。举个极端情况某种奶酪高度很小但价值极高它可能同时出现在前段和后段的最优方案里但奶酪数量无限所以这不是重复不重复的问题而是结构根本没有被正确拆分。更深层的错误在于真实规则并不是“高度超过 K 的部分打五折”而是“触发点以及触发点以上的所有奶酪打五折”。触发点以上可能只占塔的一小部分也可能占一大半这个分界线的位置是由具体方案决定的不能提前用 K 一刀切。2.3 错误做法二先全价堆满再从某个高度切换半价还有一种思路是枚举“切换高度 mid”mid 以下的奶酪全价mid 以上的奶酪半价然后答案取 f[mid] half[T - mid] 的最大值其中 half 是用半价价值跑出来的完全背包。这个思路方向是对的它已经隐约意识到了“分段”的必要性。但它缺了一个关键约束切换点不是随便选一个高度就行的切换点的位置必须满足“从下半段顶部再放一块奶酪累计高度第一次跨过 K”。换句话说如果下半段高度是 mid用来触发的那块奶酪高度必须至少是 K - mid。如果不加这个限制枚举 mid 时可能把根本没触发 K 的塔也当成半价塔计算或者把触发点放错位置算出一个现实里不存在的方案。我之前的第一版代码就栽在这里。我天真地写了这样一个循环for (int mid 0; mid T; mid) { ans max(ans, f[mid] half[T - mid]); }样例能过但一提交就 WA。原因就是上面说的mid 和上半段之间缺少一个“真正的触发奶酪”导致很多非法方案混进来了。这个坑解法很简单但如果你没有意识到会在错误的思路里绕很久。3. 正解的核心把塔拆成“全价段”和“半价段”3.1 第一块顶破 K 的奶酪是唯一的切分点绕了一圈回到正确思路上来。不管是理解题目还是写代码都必须抓住一个事实任何一座总高度达到或超过 K 的塔都一定存在唯一的一块奶酪它是从下往上数第一块让累计高度达到或超过 K 的奶酪。这块奶酪可能很矮放在下半段上面小小的一块就顶破了 K也可能很高第一块就直接超过 K。有了这块“触发奶酪”整座塔就可以干脆地分成三段触发奶酪下面的部分高度为 x这一段里所有奶酪都保持原价而且因为这一段总高度小于 K所以它内部不可能再触发减半触发奶酪本身半价高度为 h[i]美味值为 v[i]/2触发奶酪上面的部分高度为 rest这一段里所有奶酪也都是半价因为它们全在触发点之上。下面一段用“原价完全背包”算上面一段用“半价完全背包”算触发奶酪单独枚举。这就是本题最干净的状态划分方式。3.2 下半段用原价背包上半段用半价背包具体来说我们需要提前准备好两个 DP 数组dp[h]高度恰好为 h 时所有奶酪都按原价计算能拿到的最大美味值half[h]高度恰好为 h 时所有奶酪都按半价 v[i]/2 计算能拿到的最大美味值。两个数组都用完全背包的写法跑出来区别只是价值用的是 v[i] 还是 v[i]/2。C 里 v[i]/2 会自动向下取整正好符合题意。然后枚举触发奶酪 i 和下半段高度 x。注意这里的约束条件非常关键下半段高度 x 必须小于 K因为下半段一旦达到或超过 K就说明触发点应该出现在下半段内部而不是当前枚举的这块奶酪触发奶酪本身的高度 h[i] 必须满足 x h[i] K这样才能保证它确实是“第一块顶破 K”的奶酪上半段剩余高度 rest T - x - h[i] 必须大于等于 0因为整座塔高度不能超过 T。当这三个条件同时满足时这座塔的总价值就是dp[x] v[i]/2 half[rest]对所有满足条件的 i 和 x 取最大值再和“整座塔高度小于 K、完全没触发减半”的合法全价塔比较就能得到正确答案。3.3 为什么下半段的高度必须小于 K很多第一次做这题的人会问下半段高度 x 为什么非要限制在 K 以下你可以反着想想如果允许 x 大于等于 K那么下半段内部其实已经有一块奶酪触发了减半条件。你现在枚举的这块奶酪它在塔里的位置已经处于“半价区”它不能再按 v[i]/2 去当什么“触发奶酪”因为真正的触发奶酪在下面更早的位置。强行按当前公式计算就会把触发点放错导致下面一段的价值被高估。所以正确的关系一定是x 是触发点下方所有奶酪的总高度这部分必须全部原价因此 x K 是硬性条件。这也是我之前错误做法二缺失的那条约束加上它很多非法方案就被自然过滤掉了。4. 枚举触发点的C实现每一行转移都在干什么4.1 完整可提交代码下面这版代码可以直接提交到洛谷 P2979用 C17 编译。为了避免数组越界我把数组大小开到 T5 以上实际数据范围 T 不超过 100非常宽松。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, T, K; cin N T K; vectorint h(N), v(N); for (int i 0; i N; i) { cin h[i] v[i]; } vectorint dp(T 1, 0), half(T 1, 0); // dp[h]: 高度恰好为 h全部按原价 v[i] 计算的完全背包 // half[h]: 高度恰好为 h全部按半价 v[i]/2 计算的完全背包 for (int i 1; i T; i) { for (int j 0; j N; j) { if (i h[j]) { dp[i] max(dp[i], dp[i - h[j]] v[j]); half[i] max(half[i], half[i - h[j]] v[j] / 2); } } } int ans 0; // 情况一整座塔高度小于 K从不触发减半全部原价 for (int x 1; x min(T, K - 1); x) { ans max(ans, dp[x]); } // 情况二枚举触发奶酪 i 和下半段高度 x for (int i 0; i N; i) { for (int x 0; x K; x) { if (x h[i] K) continue; // 触发奶酪并没有顶破 K不合法 int rest T - x - h[i]; // 触发奶酪以上还能用的高度 if (rest 0) continue; // 高度超限跳过 int value dp[x] v[i] / 2 half[rest]; ans max(ans, value); } } cout ans \n; return 0; }4.2 两个背包的含义dp[h] 与 half[h]dp[h] 和 half[h] 虽然都是用完全背包跑出来的但它们代表的是两个平行世界一个世界里所有奶酪永远原价另一个世界里所有奶酪永远半价。真实奶酪塔是“先处于原价世界放完下半段之后突然切换到半价世界”所以这道题的答案就是这两个世界的最优值拼起来。这里有个很容易忽略的细节dp[x] 表示高度“恰好”为 x 时的最大原价价值而不是“不超过 x”的最大价值。为什么用恰好因为枚举 x 时下半段真实高度就是 x触发奶酪必须正好放在这段之上它的累计高度 x h[i] 才有意义。如果你用了“不超过 x”的背包值那后半段的计算基准就错了。完全背包天然支持“恰好”这种状态因为初始只有 dp[0] 是合法的 0其他状态必须通过一块一块奶酪累加得到。half[rest] 同理它表示触发奶酪上方“恰好”堆到高度 rest 时的最大半价价值。rest 可以取 0half[0] 就是 0表示触发奶酪上方什么也不放。4.3 枚举触发点时的三重条件xK、xhiK、rest0我把代码里那个三重判断单独拎出来讲因为它就是这道题的灵魂。第一个条件 x K下半段必须是全价段。x 一旦等于 K说明整个下半段本身就该触发减半了那真正的触发点在下半段内部当前枚举的奶酪根本不该承担“触发”职责整个状态划分就被破坏了。第二个条件 x h[i] K这块奶酪必须真的把累计高度顶破 K。如果 x h[i] 还不到 K那它没有触发任何东西真实塔里它和它上面的奶酪应该全部保持原价你用 v[i]/2 去算它就白白损失了价值。有人说那这个情况交给后面的全价分支处理不就行了对所以这里直接 continue 掉不参与半价计算。第三个条件 rest 0这是高度上限约束。rest 表示剩余可用高度如果为负数说明下半段加触发奶酪已经超过 T 了方案非法。这三个条件缺一不可。少了任何一个答案都会偏大因为你会把不存在的“半价方案”或者“触发方案”算进去。4.4 复杂度与数据范围为什么敢这么枚举看一眼数据范围N 100T 100K T。两个完全背包的复杂度是 O(N * T)就是 100 * 100一万次操作。枚举触发奶酪和下半段高度是 O(N * K)也就是 100 * 100又是一万次操作。加起来完全可以忽略不计。这个复杂度意味着本题其实不需要任何优化直接暴力枚举就是正解。我在做这题的时候反而提醒自己不要一上来就想着二分答案、单调队列优化之类的骚操作。信奥题里数据范围本身就是线索T 和 N 只有 100明显就是让你放手去枚举的。如果看到 100 还非要写 O(N^3) 的优化那就是和自己过不去。5. 边界条件与实测调试这些坑提交时才意识到5.1 “不超过 T”不等于“恰好等于 T”这是个非常容易踩的坑。题目说的是塔的总高度“不超过 T”不是“恰好等于 T”。但很多完全背包模板习惯性地用 dp[T] 当答案因为普通物品价值为正时堆得越高越好最优解往往就是恰好 T。本题加上减半规则之后这个直觉彻底失效了。举个例子。假设 T 9K 8只有一种奶酪高度 6价值 100。如果高度必须恰好等于 9那根本堆不出来因为 6 加 6 等于 12 超过 9。但题目允许高度小于 T所以最优解就是放一块奶酪高度 6价值 100。我的代码里枚举触发点时 rest T - x - h[i] 仅仅表示“还能用多少高度”并不是强制要求必须用满。如果 rest 用不满那就空着完全合法。这个设计正好贴合“不超过 T”的题意。另外全价分支我特意写了for (int x 1; x min(T, K - 1); x)也是在覆盖“塔高度小于 K 但是没堆满 T”的情况。5.2 K1、单种奶酪、rest 为负这些极端情况调试的时候我专门拿极端数据测了几组全价分支和半价分支的行为都很关键。K 1 时min(T, K-1) 0全价分支循环直接不执行。这是对的因为任何一块奶酪放下去高度至少是 1累计高度立刻达到 K所以任何非空塔都必然触发减半不存在全价塔。半价分支里x 只能取 0x h[i] 1 必然成立rest T - h[i]代码会正确计算“整座塔从第一块开始就全部半价”的最优值。注意所有奶酪高度都是正数所以这个逻辑是完备的。只有一种奶酪时比如 h5v10T20K12。最优方案是堆 4 块累计高度 20。从下往上第 3 块触发前两块全价 20第 3、4 块半价 5510总价值 30。代码里枚举触发点 i 只有一种x 从 0 到 11满足 x512 的 x 有 7、8、9、10、11其中 x10 时 rest20-10-55half[5]5dp[10]20总价值 205530。验证通过。rest 为负的情况。比如上面的例子里如果枚举 x15但 x 必须小于 K12根本进不了循环所以实际不会被卡。但保险起见代码里仍然写了 rest 0 的判断因为这个判断在处理 x 较大、h[i] 也较大的情况时能防止访问数组负数下标。5.3 用手算样例验证正确性的方法我调试这类 DP 题有个习惯不看答案先自己手算一组小数据把每一种合法方案列出来再让代码去对答案。比如我构造过这样一组数据N2, T10, K6 奶酪A: 高度4, 价值10 奶酪B: 高度3, 价值7手动枚举所有合法塔形两块 A高度 8触发点在第 2 块价值 10 5 15一块 A 一块 B高度 7如果先 A 后 B触发点是 B价值 10 3 13先 B 后 A 也一样7 5 12取 13三块 B高度 9价值 7 3 3 13高度小于 6 的单块奶酪A 价值 10B 价值 7。所以正确答案是 15。代码跑出来dp[4] 10half[4] 5枚举触发点 Ax4xh[A]86rest2half[2]0ans 10 5 0 15正确。这种手算验证虽然笨但能让你对状态划分的理解扎实很多后期写更难的分层 DP 时也不会慌。6. 从 P2979 延伸出去阈值触发类背包的通用套路6.1 变体触发点换成“从塔底到触发点全部半价”如果把规则改成“一旦达到 K从塔底到触发点之间所有奶酪半价触发点以上原价”状态划分思路依然成立只需要交换一下两个背包的使用方式。我会让下半段用半价背包触发奶酪和上半段用原价背包枚举方式不变。这个变体建议大家自己推一遍能帮你确认是不是真正理解了“切分点”的本质而不是只背住了这题的转移公式。6.2 变体触发条件换成奶酪数量而不是高度如果触发条件不是“累计高度达到 K”而是“奶酪数量达到 K”那 DP 数组的维度就要从“高度”改成“数量”同时还要保留“总高度不超过 T”的约束。这时候就变成二维状态 dp[cnt][h]转移时同时增加数量和高度。这种题目在信奥里也不少核心还是那个道理凡是存在“某个条件首次满足”的规则就要考虑把它作为状态切分点而不是试图用一个单调 DP 硬扛。6.3 刷题层面的迁移判断什么时候该拆状态做完 P2979我最大的收获不是学会了一个新 DP 模板而是强化了一个判断当题目里出现“首次达到阈值”“一旦满足就改变后续收益”这类全局条件时第一反应应该是思考这个条件会把状态空间切成几段而不是急着写转移方程。一个实用的判断标准是如果同一个“高度/容量/数量”对应多种不同的后续规则那你就必须为每种规则单独维护一个 DP 数组。P2979 里高度 h 既可能是全价塔也可能是半价塔所以必须拆成 dp 和 half 两个数组。你后面做更多题会发现这种“按规则阶段拆状态”的思路在状态机 DP、分层图最短路、区间 DP 里都很常见。最后说点个人经验。P2979 不是那种考你奇技淫巧的题它考的就是你能不能冷静地把一个看似简单的规则拆清楚。我第一版代码写完后并没有马上改而是拿了张纸把一座塔从底到顶每一块奶酪的高度和价值都标出来再对照题目规则看触发点到底在哪这才发现“第一块顶破 K”这个点一直被我想当然了。如果你也在某道题上反复 WA不妨试试这个笨办法画一座具体的小塔用手算把答案推出来再让代码逐行对应很多模糊的理解会瞬间变得清晰。这套方法比多刷十道模板题都管用。