LOJ 6515《贪玩蓝月》这题光看名字还以为又是哪个网页游戏的推广题点进去才发现是一个相当典型的“数据结构套背包”模型。题目让你维护一个双端队列队列里每个物品有重量 w 和价值 v你需要在队首、队尾任意加东西、删东西然后随时回答在当前队列中选一些物品容量不超过 c 的时候最大总价值是多少。说白了就是一个支持双端插入删除的 01 背包查询。这题我第一次见的时候第一反应是用线段树分治离线做后来发现有更漂亮的双栈在线做法思路简单、常数小、还很好写特别适合拿来练手。1. 题意与核心难点1.1 题目实质拆解把操作抽象一下队列中的每个元素就是一个“物品”物品有两个属性w重量或者叫体积v价值或者叫魅力值。操作分四种在队首插入一个物品在队尾插入一个物品从队首弹出一个物品从队尾弹出一个物品。每次询问给一个容量上限 c要求从当前队列中选若干物品让总重量不超过 c并且总价值最大。注意是“当前队列”也就是说每次插入和删除都会影响后续查询的答案。这题的难点不在于背包本身而在于“删除”。普通的 01 背包我们只会往 DP 数组里加物品不会删物品。加物品很容易因为转移是向下的从旧状态推出新状态。可一旦要删掉某个物品问题就麻烦了你不能简单地把这次转移“逆运算”回去因为同一个 DP 值可能是多种物品组合得到的删除一个物品后你根本不知道哪些状态是依赖它更新出来的。1.2 为什么不能直接做可撤销背包很多人第一反应是写一个“带撤销的背包”每个物品入栈时记录它改动了哪些位置撤销的时候再把这些位置恢复。对单个栈来说这确实是可行的push 时记录修改pop 时回滚。但这里是双端队列两端都能进出靠一个栈根本模拟不了。退一步讲就算你用两个栈硬模拟查询的时候还需要把两个栈里的物品合并。合并两个背包的朴素做法是枚举两侧各自选了多重也就是 O(C^2)。如果 C 是几百、操作是几万次O(操作数 * C^2) 直接超时。所以核心就变成了两个问题怎么让“双端队列”的插入删除变得可维护怎么让“合并两个背包”的代价降下来。双栈模型恰好能同时解决这两个问题。2. 用两个栈还原双端队列2.1 栈顶朝外的双栈设计栈和队列最大的区别是栈只能在一端进出队列是两端进出。一个栈没法模拟队列但两个栈可以。经典的队列用两个栈实现是“一个负责进、一个负责出”查询时只用到两个栈的 DP 值不需要真的把队首队尾连起来。对于双端队列我习惯这样的设计左栈 L栈顶代表队首方向右栈 R栈顶代表队尾方向。示意图可以理解为队首方向 队尾方向 L顶 → L底 R底 → R顶左右两个栈的栈底靠在一起。这样push_front直接压入 L新元素变成新的队首push_back直接压入 R新元素变成新的队尾pop_front弹 L 的栈顶pop_back弹 R 的栈顶。这个设计下两个栈的栈顶都朝队列外面栈底都朝中间所以任意一端插入弹出都只影响对应栈的栈顶天然支持 O(1) 的单次栈操作。2.2 翻倒操作与摊还代价但是问题来了如果 pop_front 的时候 L 是空的而 R 里有元素队首其实在 R 的栈底方向这时候你没法直接弹 R 的栈底。解决办法是把 R 里的元素全部倒进 L。R 的栈顶是队尾方向从 R 弹出元素的顺序是队尾、倒数第二个、……、队首。这些元素依次压入 L 之后L 的栈顶恰好就是原来的队首。所以执行while (R非空) { L.push(R.top()); R.pop(); }之后 L 从栈顶到栈底就是原来的队首到队尾此时再 L.pop() 就可以删掉真正的队首了。反过来pop_back 时若 R 空就把 L 全部倒进 R操作是对称的。这个翻倒过程看起来每次都要搬一大堆元素会不会总复杂度爆炸不会这就是经典的摊还分析。任何一个元素从 R 倒进 L 之后它要么在 L 里被弹出要么下次再被倒回 R。一个元素每次“倒”都会换一个栈而每个栈在被倒空之前另一侧必为空。实际上每个元素在整个生命周期里只会被翻倒常数次总翻倒次数是 O(n) 级别的。要注意的是我们这里每个“栈顶元素”本身就是一件物品而每个物品进出栈时都要更新对应栈的背包 DP所以翻倒的代价不是 O(1)而是 O(C)因为每搬一次物品就要用它做一次背包转移。这一点的摊还分析在后面会一起算。3. 栈内背包 DP 的维护3.1 增量式更新push 时顺带做转移两个栈各自维护一个 DP 数组。以左栈 L 为例假设 L 当前有 k 个元素我用f_L[i][j]表示考虑 L 的栈底到当前第 i 个元素也就是 L 里任意 i 个元素的组合中重量恰好为 j 时能得到的最大价值。你可能觉得栈底到栈顶的顺序会影响 DP 结果其实不会。背包问题只关心“哪些物品可用”不关心物品的先后顺序。所以每次 push 新物品时只需要在旧 DP 数组的基础上用这个新物品做一次 01 背包转移arrayint, MAXC cur pre; // 不选新物品的情况 for (int j 0; j w C; j) { if (pre[j] ! NEG) { cur[j w] max(cur[j w], pre[j] v); } }注意这里一定用的是pre[j]不是cur[j]。因为 pre 表示“加入这个物品之前”的状态。如果误用 cur[j]同一个物品就会被重复取多次变成完全背包了。每次 push 之后把这个 cur 存到历史数组里。这样 pop 的时候只需要丢掉历史数组的最后一层就自动回到了加入上一个物品之前的状态这就是可撤销的关键。3.2 查询时如何合并两个栈查询容量不超过 c 时左栈贡献一部分重量 i右栈贡献剩余重量 j总重量 i j 不超过 c。如果直接枚举 i 和 j复杂度是 O(C^2)。但我们可以先处理右栈的“前缀最大值”pref[0] B[0]; for (int j 1; j c; j) { pref[j] max(pref[j - 1], B[j]); }pref[j] 表示右栈中选出总重量不超过 j 时的最大价值。然后枚举左栈重量 ifor (int i 0; i c; i) { if (A[i] ! NEG) { ans max(ans, A[i] pref[c - i]); } }这样查询就是 O(C) 的。如果题目要求“重量恰好为 c”那就更简单直接把 pref 换成 B 本身for (int i 0; i c; i) { if (A[i] ! NEG B[c - i] ! NEG) { ans max(ans, A[i] B[c - i]); } }还有一个常见优化查询时先判断两个栈哪个元素更少枚举元素多的那边做前缀最大值、元素少的这边直接枚举重量常数会更小一点。不过复杂度不变仍然是 O(C)。4. 完整实现与复杂度分析4.1 核心代码实现我习惯把栈和背包封装成一个结构体这样逻辑清楚不容易写乱。下面这份代码是“容量不超过 c”的版本如果题目要求恰好容量把 query 函数里的前缀最大值部分换成直接合并即可。#include bits/stdc.h using namespace std; const int MAXC 505; // 容量上限按题目调整 const int NEG -1e9; // 不可达状态 struct Item { int w, v; }; struct StackDP { vectorItem ele; // 栈内元素 vectorarrayint, MAXC dp; // dp[i][0..C]: 前 i 个元素的背包 StackDP() { arrayint, MAXC a; a.fill(NEG); a[0] 0; dp.push_back(a); // 空栈只有重量 0 可达 } int sz() const { return (int)ele.size(); } void push(const Item x) { const arrayint, MAXC pre dp.back(); arrayint, MAXC cur pre; // 不选 x for (int j 0; j x.w MAXC; j) { if (pre[j] ! NEG) { cur[j x.w] max(cur[j x.w], pre[j] x.v); } } ele.push_back(x); dp.push_back(cur); } void pop() { ele.pop_back(); dp.pop_back(); // 直接回退历史 } }; struct DequeDP { StackDP L, R; // L顶队首R顶队尾 void push_front(const Item x) { L.push(x); } void push_back(const Item x) { R.push(x); } void pop_front() { if (L.sz() 0) { while (R.sz() 0) { Item x R.ele.back(); R.pop(); L.push(x); } } L.pop(); } void pop_back() { if (R.sz() 0) { while (L.sz() 0) { Item x L.ele.back(); L.pop(); R.push(x); } } R.pop(); } int query(int cap) { const auto A L.dp.back(); const auto B R.dp.back(); // 对右栈做前缀最大值 vectorint pref(cap 1, NEG); int curBest NEG; for (int j 0; j cap; j) { curBest max(curBest, B[j]); pref[j] curBest; } int ans NEG; for (int i 0; i cap; i) { if (A[i] ! NEG) { ans max(ans, A[i] pref[cap - i]); } } return ans; } };这里唯一要注意的是翻倒的时候我直接访问了R.ele.back()然后立刻R.pop()再L.push(x)。因为 R 的 pop 会丢掉 R 里最后一个元素的背包历史而 L 的 push 会把同一个元素加到自己的背包历史里。这个顺序不能反先取出元素再弹栈再压入另一个栈。pop_front和pop_back的翻倒逻辑都是“目标栈为空时把另一个栈全部倒过来”。倒完之后目标栈的栈顶恰好就是要弹出的队首或队尾所以最后直接pop()就可以。4.2 复杂度到底是多少先看单次操作push_front / push_backO(C)因为要基于旧 DP 做一次背包转移pop_front / pop_backO(C)因为要弹出 dp 历史数组的最后一层数组本身的弹出是 O(1)但如果有翻倒每个被搬运的元素都会触发一次 push也就是 O(C)queryO(C)。看起来每个操作都是 O(C)但翻倒会把一次 pop 的代价放大到 O(元素个数 * C)。好在摊还下来每个元素最多被搬运常数次。为什么考虑一个元素从 R 被搬到 L搬完之后 R 为空。之后这个元素想再被搬一次必须等到 L 为空、R 里有新的元素并且又需要被搬到 L。也就是说每次大规模翻倒都会把一侧清空。元素在两侧之间切换的次数是有限的本质上每个元素只会经历“入场 → 可能被翻倒 → 出场”这个过程。总时间复杂度是 O((操作次数 翻倒搬运次数) * C)也就是 O(qC)。对比一下朴素做法如果每次查询都暴力合并两个栈一次查询就是 O(C^2)。双栈做法把查询降到了 O(C)把插入删除也控制在 O(C) 级别整体性能是质变。5. 实战中的坑与排查技巧5.1 初始化与负无穷dp[0][0] 必须初始化为 0其他位置为负无穷。这样才能表示“空栈只能组合出重量 0”。如果你把 dp[0][0] 也设成负无穷查询时所有状态都不可达答案永远是负无穷。负无穷的取值不要用-0x3f3f3f3f再加一个正数因为价值累加之后可能溢出。直接用-1e9比较稳如果价值范围很大可以考虑-4e18但记得用 long long 存。5.2 翻倒是最大事故现场翻倒最容易出 bug 的地方是方向。我一开始写的时候想当然地循环while (R.sz()) L.push(R.top())但没有先取出元素就R.pop()逻辑上没问题可代码写成了while (R.sz() 0) { R.pop(); L.push(???); }结果不知道从哪取元素直接 RE。正确流程一定是Item x R.ele.back(); R.pop(); L.push(x);另外翻倒前一定要判断目标栈是否为空。如果 L 非空你又从 R 倒过来就会把原来属于队首方向的东西和队尾方向的东西混在一起队列顺序就乱了。我在本地上测试随机数据队列顺序乱了之后查询答案经常无规律可循。5.3 空间占用与常数优化dp 历史数组是这道题内存的主要来源。每次 push 都会复制一整份容量数组如果容量 C 500一个 arrayint, 505 大约是 2 KB。队列里最多同时存在的元素个数不会超过操作数 q所以两个栈总共的内存大约是 O(qC)。如果 q 是五万、C 是五百内存不到 110 MB在很多 OJ 上能过。但如果 q 是十万、C 再大一点可能就有点紧张了。可以做的优化预估最大操作数提前L.dp.reserve(q 5)避免 vector 扩容反复拷贝在 StackDP 里只保存 dp 历史不需要保存两个完整数组如果查询是“恰好容量”可以把容量数组长度压缩到 max(c) 1而不是 MAXC。常数方面arrayint, MAXC是连续内存缓存很友好。查询时对右栈做前缀最大值的临时数组可以复用不要每次 query 都重新分配 vector。我习惯在 DequeDP 里预分配一个全局的tmp[MAXC]查询时直接使用。6. 扩展模数背包与离线分治思路6.1 如果题目变成模 m 背包有些双端队列背包题会把询问改成给定 m 和 x问选出若干物品后总重量对 m 取模等于 x 的最大价值。这时候 DP 数组长度就不再是容量上限而是模数 m。转移变化也很简单cur[(j w) % m] max(cur[(j w) % m], pre[j] v);查询时枚举左栈余数 i右栈余数就是(x - i m) % m合并 O(m)。其他逻辑完全一样。因为模 m 的余数数量通常比真实容量上限小很多这种变式反而更好写。6.2 另一条路线段树分治如果不追求在线也可以用线段树分治做。核心思路是每个物品都有一个存活时间段从插入时刻到删除时刻。把每个时间段看成一个区间覆盖到线段树的若干节点上。然后 DFS 遍历线段树进入节点时把这个节点上的物品全部加入背包离开节点时回滚加进去的物品。因为每个物品会被放到 O(log q) 个节点上加入背包一次是 O(C)总复杂度 O(q log q * C)。这个做法也很经典而且不依赖双端队列的性质很多“支持删除的背包题”都能用。但它的代价是必须离线而且空间和时间常数比双栈做法大不少。如果题目允许离线两种方法都能过如果题目强制在线双栈做法就是首选。回到《贪玩蓝月》这题本身我实际写完双栈做法后在本地用随机数据对拍过也试过几种不同的翻倒写法最后发现“栈顶朝外 空栈翻倒”这个模型是最不容易出错的。建议你拿到题之后先把队列操作和背包维护分开想清楚再动手写代码。这个套路理解透之后以后遇到“可删除背包”“双端队列加背包”之类的变体基本都能一眼看穿。