到O(nK log m)实战)
最近在写一个卡牌对战游戏的战斗模拟器时，栽在了一个看起来很简单的最优出牌规划上：牌堆从左到右一张张翻，你可以打出也可以跳过，但打出的卡牌等级必须不降，而且整个战斗最多打K张牌。攻击力显然要尽量高，所以本质是把“等级不降、位置递增、长度不超过K”的最优子序列挑出来。一开始我写了暴力DP，n到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]
如果找不到这样的 p，f[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 到 1e5，K 到 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 = 1e5，K = 8，m = 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]; vector<int> 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 小数据推演一遍，看看答案怎么来
用一组小数据验证流程。假设 n=5，K=3，卡牌信息如下：
| 位置 | 攻击 | 等级 |
|---|---|---|
| 1 | 3 | 5 |
| 2 | 2 | 3 |
| 3 | 4 | 4 |
| 4 | 1 | 2 |
| 5 | 6 | 4 |
先算第一层 dp1，就是每张牌自己的攻击力：3、2、4、1、6。接下来算 k=2 时，每张牌尝试接一个前驱。第3张牌等级4，查询前缀区间 [1,4] 时，能看到第2张牌等级3的 dp1=2，所以 dp2[3]=4+2=6。第5张牌等级4，查询前缀时能看到第2张牌等级3的 dp1=2，以及第3张牌等级4的 dp1=4，最大值是4，因此 dp2[5]=6+4=10。
再算 k=3，前驱层是 dp2。第5张牌查询前缀时能看到第3张牌的 dp2=6，于是 dp3[5]=6+6=12。这个 12 对应的实际出牌序列是：第2张牌（等级3攻击2）→ 第3张牌（等级4攻击4）→ 第5张牌（等级4攻击6）。位置递增，等级不降，攻击力总和正好是12。
最后答案取所有 f[i][k] 的最大值，也就是12。这个例子虽然小，但足够说明“先查询再插入”的顺序和前缀最值的作用。
4. 调试实录：最容易翻车的四个地方
4.1 先查询再更新，否则一张牌会被用两次
我在实际调试时踩过最大的坑，就是“边算边更”的顺序问题。如果处理到第 i 张牌时，先更新线段树，再查询前缀，那么查询结果里就可能包含第 i 张牌自己上一层的信息。举个例子，在算 k=3 时，如果先把当前牌当成上一层前驱插进去，再查询，就会构造出“同一张牌在序列里出现两次”的错误情况。结果答案会比真实值偏大，而且越到后面偏差越多。
正确的顺序必须是在每个 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 实测性能：n=100000 时的表现
我在随机数据下跑了几组测试，n=100000，K=8，等级随机分布在 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”的题目，不妨先写暴力，再观察转移能不能转成区间最值问题。这一步想通，代码量反而不会增加多少，性能却能提升几个量级。
