最近在写一个卡牌对战游戏的战斗模拟器时栽在了一个看起来很简单的最优出牌规划上牌堆从左到右一张张翻你可以打出也可以跳过但打出的卡牌等级必须不降而且整个战斗最多打K张牌。攻击力显然要尽量高所以本质是把“等级不降、位置递增、长度不超过K”的最优子序列挑出来。一开始我写了暴力DPn到10000就卡得难受后来把DP的前驱查询换成权值线段树复杂度立刻从O(n²K)降到O(nK log m)同样数据规模几乎是无感运行。这篇文章从状态设计、数据结构选型、C实现到调试经验完整过一遍适合正在啃DP优化或者卡牌对战类模拟题的读者。1. 卡牌对战规则建模与DP状态设计1.1 牌堆顺序和“等级不降”到底在限制什么很多卡牌游戏里玩家手里的牌是可以任意重排的那就没有所谓的“子序列DP”了直接按等级排序后选攻击力最大的几张就行题目也就失去了难度。这个模拟器不一样它的规则是牌堆必须按初始顺序一张一张翻翻到一张牌时只能选“打出”或“跳过”不能把后面的牌拿到前面来。换句话说你最终打出的牌在原始牌堆里的位置一定是递增的。在此基础上还有一个限制打出序列的等级必须不降。比如前一张牌的等级是3后面只能接等级大于等于3的牌如果下一张等级是2就只能跳过不能打出来。这个“等级不降”是典型的“单调性约束”它让问题从“随便选牌”变成了“带条件的最优子序列选择”。用算法语言描述就是从n张牌里找一个长度不超过K的子序列要求下标递增、等级值不减并且攻击力之和最大。所以卡牌对战只是外壳核心其实是一个带权最长非降子序列问题。很多实时对战游戏里的技能链、连击顺序、装备穿戴顺序最后都能抽象成这种模型。把规则剥开以后后面的DP设计就顺理成章了。1.2 定义 f[i][k] 与转移方程DP状态可以这样定义设 f[i][k] 表示“以第 i 张牌作为最后打出的牌并且已经打出了 k 张牌时能获得的最大总攻击力”。注意“最后打出的牌是第 i 张”这个限定非常重要因为跳过操作无法用“处理到前 i 张的一维状态”干净地表达而“结束于第 i 张”能直接指向一个明确的序列尾部。先看第一层。如果只打一张牌那么任何一张牌都可以作为序列的第一张所以初始状态是f[i][1] atk[i]当 k 2 时想以第 i 张牌结尾就必须在它前面找到一张已经打出的牌 p要求 p i并且 level[p] level[i]。前 p 张牌构成的一个长度为 k-1 的最优序列再接上第 i 张牌。于是转移方程是f[i][k] atk[i] max( f[p][k-1] )其中 p i 且 level[p] level[i]如果找不到这样的 pf[i][k] 就是不存在应该设成负无穷而不是 0。这个细节后面调试部分会专门讲很多错误答案都出在这里。最终答案是所有 f[i][k] 里的最大值因为最优序列不一定用满K张牌也不一定固定以哪张牌结尾。1.3 暴力枚举前驱的复杂度瓶颈如果不做任何优化最直白的写法就是三层循环外层枚举 k中层枚举 i内层枚举所有满足 p i 的 p再判断 level[p] level[i]。代码大概长这样for (int k 2; k K; k) { for (int i 1; i n; i) { for (int p 1; p i; p) { if (level[p] level[i]) f[i][k] max(f[i][k], f[p][k-1] atk[i]); } } }这个复杂度是 O(n²K)。当 n 只有几千时还能忍一旦 n 到 1e5K 到 8理论计算量就是 8e10在任何常规限时下都不可能跑完。问题核心在于内层 p 的循环本质上是在“所有已计算好的前驱里找满足 level 条件的最优值”。我们真正想要的不是一个具体下标而是一个“值域范围里的最大值”。这给优化指明了方向把 level 当作索引用数据结构维护“已经处理过的牌中每种等级对应的最大 f[p][k-1]”。这样每次转移就从 O(i) 枚举变成 O(log m) 查询。2. 权值线段树如何把O(n²)压到O(nK log m)2.1 把转移转化成前缀最值查询在固定 k 的情况下我们需要的是 max(f[p][k-1])其中 p i 且 level[p] level[i]。如果按牌堆顺序 i 从小到大处理那么当处理到第 i 张时所有 p i 的上一层状态都已经算好可以插入到数据结构里。这个数据结构以 level 为键以 f[p][k-1] 为值。每次只需要查询所有 level 小于等于 level[i] 的最大值也就是查询值域区间 [1, rank[i]] 上的最大值。这正是一个典型的前缀最值查询。为什么是前缀因为条件是 level[p] level[i]把所有等级离散化成从小到大排好的 rank 后符合条件的等级集合一定是从最小值到当前等级的连续区间。所以我们只需要在权值线段树上做一次区间查询就可以拿到最佳前驱的总攻击力再加 atk[i] 就完成转移。这个过程还隐含了位置顺序的维护因为数据是一张一张按顺序插入的插入到某个等级的牌它的位置一定在当前处理的 i 之前。数据结构本身不存位置下标但插入顺序天然保证了“位置递增”的限制。2.2 为什么这里选权值线段树而不是树状数组权值线段树和普通线段树的区别在于建树的“下标”是什么。普通线段树下标是数组位置比如 1 到 n权值线段树下标是数据值本身比如卡牌的各种等级。因为等级可能很大而且很稀疏需要先离散化把可能出现的等级映射到 1 到 m 的连续整数再在这个值域上建线段树。每个叶子表示一种等级每个节点维护这个等级区间内的“最优值”。在这个题目里查询固定是前缀其实树状数组也可以做前缀最大值和点更新最大值的操作复杂度同样是 O(log m)。那为什么我还推荐权值线段树因为后续扩展太方便。如果游戏规则改成等级区间在一个范围 [L, R] 内树状数组就不好处理任意区间最值而线段树直接改一下查询函数就行。如果以后要处理多个维度、多棵线段树、甚至可持久化版本权值线段树的灵活性也明显更高。另外权值线段树的“点更新 区间查询”和 DP 转移天然契合每张牌对应一次点更新每个状态转移对应一次区间查询。我们可以把整个数据结构理解成一个“支持按等级范围快速取最大值的动态表”它的存在让原来最耗时的内层 p 枚举消失了。2.3 从暴力到优化的复杂度对照暴力DP是 O(n²K)。权值线段树优化后每个 k 层对每张牌做一次查询一次更新所以复杂度是 O(K n log m)其中 m 是离散化后的等级数量m 最多等于 n。预处理阶段需要排序和去重复杂度 O(n log n)在整个规模里可以忽略。空间方面如果直接用二维 f 数组是 O(nK)如果使用滚动数组是 O(n m)。权值线段树本身用 4m 大小的数组存储在 n 1e5 时非常轻松。我随手估算过一组数据n 1e5K 8m 1e5。每张牌一次查询一次更新线段树两层操作大约需要 17 次左右递归总操作量在 2e7 这个量级。C 开启 O2 以后单组数据跑完基本在 0.3 秒上下。这个量级在真实项目中也是可以接受的。3. 可直接复现的C实现与推演3.1 离散化等级把值域收进 1..m因为卡牌等级可能很大比如从 1 到 1e9直接开数组不现实所以第一步要把所有出现过的等级收集起来排序去重得到唯一等级列表。然后每个原始等级用 lower_bound 找到它在列表中的位置从 1 开始编号。离散化后叶子节点的数量就是 m。等级值本身不再参与线段树的区间比较而只使用 rank 这个相对顺序。这样做不会丢失大小关系rank 小的一定对应原始等级小rank 大的对应原始等级大。所以原来的条件 level[p] level[i] 就变成了 rank[p] rank[i]查询前缀 [1, rank[i]] 即可。如果等级是浮点数或者字符串只要定义好比较规则离散化逻辑完全一样。权值线段树不关心值本身只关心值之间的相对顺序这让它能应对各种奇奇怪怪的卡牌属性。3.2 核心代码滚动DP单棵权值线段树这里我采用滚动数组而不是开 K 棵线段树。原因很简单计算当前层 k 时只需要上一层 k-1 的数据不需要保留所有历史层。下面的代码里dpPrev存的是上一层结果dpCur存的是当前层结果线段树每次只用来插入和查询上一层的前驱状态。#include bits/stdc.h using namespace std; const int MAXN 100005; const int NEG -1e9; int n, K, m; int atk[MAXN], lev[MAXN], rk[MAXN]; int dpPrev[MAXN], dpCur[MAXN]; vectorint allLev; int seg[MAXN 2]; void update(int o, int l, int r, int pos, int val) { if (l r) { seg[o] max(seg[o], val); return; } int mid (l r) 1; if (pos mid) update(o 1, l, mid, pos, val); else update(o 1 | 1, mid 1, r, pos, val); seg[o] max(seg[o 1], seg[o 1 | 1]); } int query(int o, int l, int r, int ql, int qr) { if (ql l r qr) return seg[o]; int mid (l r) 1; int res NEG; if (ql mid) res max(res, query(o 1, l, mid, ql, qr)); if (qr mid) res max(res, query(o 1 | 1, mid 1, r, ql, qr)); return res; } int main() { scanf(%d%d, n, K); for (int i 1; i n; i) { scanf(%d%d, atk[i], lev[i]); allLev.push_back(lev[i]); } sort(allLev.begin(), allLev.end()); allLev.erase(unique(allLev.begin(), allLev.end()), allLev.end()); m (int)allLev.size(); for (int i 1; i n; i) { rk[i] lower_bound(allLev.begin(), allLev.end(), lev[i]) - allLev.begin() 1; } int ans 0; for (int i 1; i n; i) { dpPrev[i] atk[i]; ans max(ans, atk[i]); } for (int k 2; k K; k) { fill(seg, seg 4 * m 5, NEG); for (int i 1; i n; i) { int best query(1, 1, m, 1, rk[i]); if (best NEG / 2) dpCur[i] atk[i] best; else dpCur[i] NEG; ans max(ans, dpCur[i]); // 关键插入的是上一层的 dpPrev[i]不是刚算出来的 dpCur[i] if (dpPrev[i] NEG / 2) update(1, 1, m, rk[i], dpPrev[i]); } for (int i 1; i n; i) { dpPrev[i] dpCur[i]; } } printf(%d\n, ans); return 0; }这段代码里最容易被忽略的地方是update( ... , dpPrev[i])。这里插入的必须是上一层 dpPrev也就是长度为 k-1 的最优值。如果把当前这层刚算出的 dpCur 插进去线段树里就会混入长度错误的序列后面所有转移都会算错。3.3 小数据推演一遍看看答案怎么来用一组小数据验证流程。假设 n5K3卡牌信息如下位置攻击等级135223344412564先算第一层 dp1就是每张牌自己的攻击力3、2、4、1、6。接下来算 k2 时每张牌尝试接一个前驱。第3张牌等级4查询前缀区间 [1,4] 时能看到第2张牌等级3的 dp12所以 dp2[3]426。第5张牌等级4查询前缀时能看到第2张牌等级3的 dp12以及第3张牌等级4的 dp14最大值是4因此 dp2[5]6410。再算 k3前驱层是 dp2。第5张牌查询前缀时能看到第3张牌的 dp26于是 dp3[5]6612。这个 12 对应的实际出牌序列是第2张牌等级3攻击2→ 第3张牌等级4攻击4→ 第5张牌等级4攻击6。位置递增等级不降攻击力总和正好是12。最后答案取所有 f[i][k] 的最大值也就是12。这个例子虽然小但足够说明“先查询再插入”的顺序和前缀最值的作用。4. 调试实录最容易翻车的四个地方4.1 先查询再更新否则一张牌会被用两次我在实际调试时踩过最大的坑就是“边算边更”的顺序问题。如果处理到第 i 张牌时先更新线段树再查询前缀那么查询结果里就可能包含第 i 张牌自己上一层的信息。举个例子在算 k3 时如果先把当前牌当成上一层前驱插进去再查询就会构造出“同一张牌在序列里出现两次”的错误情况。结果答案会比真实值偏大而且越到后面偏差越多。正确的顺序必须是在每个 i 上先做 query再 update。query 使用的线段树里只包含位置小于 i 的牌update 之后再往后处理时第 i 张牌才能成为后续牌的前驱。这个顺序不是性能细节而是正确性细节。还要注意update 插入的是 dpPrev[i]而不是 dpCur[i]。因为当前正在计算的是长度 k 的序列能作为它的前驱的必须是长度 k-1 的序列。如果把 dpCur 插入相当于把长度 k 的序列当成 k-1 层使用长度信息就乱了。4.2 失败态必须用 -INF不能用 0 充数暴力DP里很多时候偷懒会把数组初始化为0。如果攻击力全是正数0 确实不会比任何合法序列大但它会出现一个隐蔽问题当不存在长度为 k-1 的合法前驱时如果 best 返回 0代码会以为前面已经打出了 k-1 张牌于是 f[i][k] atk[i] 0相当于只算了一张牌的攻击力却把它记成了长度为 k 的序列。这样算出来的 k 层状态是假的后面的转移全部会被污染。正确做法是设置一个足够小的负无穷 NEG。只有 query 返回值大于 NEG/2 时才认为存在合法前驱否则 f[i][k] 维持 NEG也就是不存在这个状态。代码里的best NEG / 2判断就是为了过滤这种无效转移。4.3 重复等级别直接覆盖要用 max 合并权值线段树的每个叶子对应一种等级而不是一张卡牌。如果有两张牌的等级相同它们会映射到同一个 pos。此时点更新不能直接赋值因为后处理的牌不一定比先处理的牌更优。应该使用seg[o] max(seg[o], val);这样才能保留这个等级下的最优 dp 值。由于处理顺序天然保证位置递增同一等级内部不必再比较位置先后只要当前查询的 i 大于之前插入的所有同等级牌它们都满足 p i。如果使用直接赋值而不是取 max同一个等级里后面出现的低攻击力牌会把之前的高攻击力牌覆盖掉导致答案偏小。这个问题在暴力DP里看不出来因为暴力是按位置逐个比较的不会因为等级合并而丢失信息。4.4 实测性能n100000 时的表现我在随机数据下跑了几组测试n100000K8等级随机分布在 100000 个不同值里。开启 O2 优化后单组数据完成全部 DP 大约在 0.3 到 0.5 秒。空间上dpPrev 和 dpCur 各占 100000 个 int线段树节点数约 4 倍 m整体内存不超过 3MB。如果把这份代码放到一般在线评测环境或者比赛环境里时间都是非常充裕的。唯一需要注意的是递归线段树在极端情况下可能栈开销较大不过 n 只有 1e5 时深度大约是 17 层完全不用改写成迭代版。如果 n 到 1e6再考虑用循环展开或者迭代线段树。5. 这种“DP权值线段树”还能用在哪儿5.1 带限制的最优子序列问题这个项目的核心套路是一个带位置顺序和属性单调限制的最优子序列问题如果转移里需要反复求“前驱的最优值”就可以把前驱状态按某个属性建立权值线段树。最经典的例子是 LIS 的带权版本给定 n 个物品每个物品有权重和价值要求下标递增、权重不减求最大价值和。这和我写的卡牌题目几乎同构。类似的场景还有任务调度任务必须按时间顺序执行并且优先级不能下降每个任务有收益选择不超过 K 个任务。做一次模型抽象之后DP 方程一模一样直接套用权值线段树优化即可。5.2 从前缀查询扩展到任意区间与多维约束如果卡牌规则不是“等级不降”而是“等级必须落在 [L, R] 区间内”代码只需要把 query 的区间从[1, rank[i]]改成[L, R]其余部分不需要动。权值线段树天然支持任意区间最值查询这也是它比树状数组更稳的原因之一。如果约束从一维变成二维比如要求攻击和费用两个属性都不超过限制那就要考虑二维数据结构或者 CDQ 分治。权值线段树可以作为内层结构配合外层按另一个属性排序来处理这类偏序约束。只要转移方程能写成“某个属性范围里的最优前驱”这套思路就能继续用。5.3 如果K特别大或数据动态变化怎么办当 K 很大时滚动数组的时间复杂度 O(K n log m) 可能会成为瓶颈。这时可以观察问题是否满足凸性或者使用矩阵快速幂加线段树去加速某些特殊转移但这属于进阶优化不一定是所有卡牌题都需要。如果卡牌不是一次性给完而是会动态加入或删除权值线段树也可以换成动态开点或平衡树。删除操作需要额外维护每个叶子里可能的多条信息常见做法是叶子堆或者 set。对于竞赛题来说动态版本少对于真实项目来说数据结构的选择就要更灵活。我自己做完这个模拟器之后最大的感受是DP优化的本质是想办法把转移式中反复计算的那部分公共信息提取出来。权值线段树只是其中一个实现手段关键在于先看出“前驱最优值”其实是一个区间查询。如果你之后再遇到“看起来像卡牌、实际上是序列DP”的题目不妨先写暴力再观察转移能不能转成区间最值问题。这一步想通代码量反而不会增加多少性能却能提升几个量级。