CodeForces-946G 这题我第一眼看到名字以为是普通的 LIS 变种但真正写起来才发现坑全藏在“删除一个元素”这个看似微不足道的改动里。网上不少题解直接给了 DP 方程却没讲清楚为什么偏移量会从b[i] a[i] - i变成b[i] 1导致很多人抄代码都抄不明白。这篇文章把完整的推导链条补上附带可直接 AC 的 C17 实现以及我用暴力对拍踩过的几个典型错误希望能帮你在赛场上省下半小时。如果你已经会经典的最少修改次数问题n - LIS可以直接跳到第 3 节看删除情况的处理如果还不熟悉我建议从头读因为后面的两个偏移量判定实际上都建立在经典做法之上。1. 先说结论这题到底在考什么题目大意非常简洁给一个长度为n的数组你可以先删除至多一个元素然后把任意位置的元素改成任意整数每次修改算一次操作目标是让最终序列严格递增求最小操作次数。数据范围一般是n到2e5a[i]到1e9所以正解必须是O(n log n)。表面上看这就是经典题“通过修改使数组严格递增”加了一个删除操作很多人第一反应是枚举删除哪个位置然后对剩下的数组跑一遍n - LIS取最小值。这个思路复杂度是O(n^2 log n)直接超时而且它忽略了一个致命细节——删除元素后剩余元素的相对下标发生了错位经典的a[i] - i偏移量不再统一适用。这题真正的考点就是如何把“删除一个元素”造成的下标偏移用两个状态、两组判定条件编码进 DP 里。最终答案也很漂亮设best是允许删除至多一个元素时能保留且不改动的最长递增子序列长度则最小操作次数就是n - best。为什么这里的删除操作没额外算一次因为删除本身算一次操作但删除之后少了一个需要修改的元素删除消耗和修改省下的次数正好抵消。这个结论在 dp 状态里天然成立不需要单独讨论。2. 经典版回顾为什么答案是 n - LIS先把没有删除操作的原版问题彻底吃透这是理解 946G 的地基。一个整数序列要严格递增意味着对于任意保留位置i j必须满足a[i] a[j]。由于元素都是整数更精确地说相邻两个保留元素之间至少要相差 1。如果这两个保留元素在原数组中的下标距离是d j - i那么它们在最终序列里中间还夹着d - 1个元素这些元素可能被修改所以值域跨度至少要满足a[j] - a[i] d j - i移项后得到a[i] - i a[j] - j这就是为什么所有题解都会令b[i] a[i] - i然后求b的最长非递减子序列长度L。答案n - L是最少修改次数因为保留L个元素不动剩下n - L个元素都改掉总能找到合适的整数填补它们之间的空当。这里有一个容易误会的点b数组求的是“非递减”而不是“递增”因为转化后允许b[i] b[j]它对应原数组中相邻保留值恰好相差下标距离的情况。比如a [1, 2, 3]b [0, 0, 0]非递减 LIS 长度为 3完全正确。如果用求严格递增反而会得到 1那就错了。从 LIS 的角度理解这件事也很直观我们要挑选尽量多的原数组元素保持原值这些被挑选的元素本身必须能“塞进”一个严格递增序列b[i] a[i] - i就是给每个元素扣掉它在新序列里应该占的“位置租金”剩下的是它相对标准递增轴的“富余量”。富余量非递减才能保证没有重叠或回退。经典问题弄懂后再看允许删除一个元素的情况你会发现在b的计算里每个保留元素应该扣掉的下标取决于它前面实际删除了几个元素。3. 删除一个元素后判定条件要分裂成两个现在给经典模型加一个删除操作。设最终保留序列中的两个相邻保留位置在原数组中的下标为j和i且j i中间隔着i - j - 1个元素。古典情形下这中间的i - j - 1个元素全部通过修改保留在最终序列里所以空间要求是a[j] - j a[i] - i。现在允许删除一个元素分两种情况讨论。情况 A删除位置在j之前包括在保留序列第一个元素之前这时j和i之间没有任何元素被删除中间那些元素仍然全部需要修改填补。j和i都在“已删除一个元素”这个事实之后它们的下标偏移都要加 1即应该用b[i] 1和b[j] 1来比较。两个偏移量同时加 1比较结果不变b[j] 1 b[i] 1 ⟺ b[j] b[i]所以这种情况下保留条件跟经典版完全一致b[j] b[i]。情况 B删除位置发生在j和i之间这是本题的核心。中间原本有i - j - 1个元素现在被删掉了一个只剩i - j - 2个元素需要修改后留在最终序列里。也就是说j和i在新序列中需要拉开的距离比经典情况下少了 1因此值域跨度要求可以放松一档a[i] - a[j] (i - j - 2) 1 i - j - 1移项a[j] - j a[i] - i 1写成b的记号就是b[j] b[i] 1这多出来的 1就是那个被删除元素空出来的“位置租金”。很多题解直接说删除后要用b[i] 1作为查询 key原因就在这里——它不是拍脑袋而是严格推导出来的空间条件。根据这两种情况我们定义两个 DP 状态dp0[i]以原数组第i个元素结尾没有删除任何元素时能保留的最大长度。dp1[i]以原数组第i个元素结尾已经删除过一个元素且删除位置在i之前时能保留的最大长度。转移方程如下dp0[i] 1 max{ dp0[j] | j i and b[j] b[i] } dp1[i] max( 1, // 删除 i 前面某个元素后只保留 i 自己i2 时合法 1 max{ dp1[j] | j i and b[j] b[i] }, // 情况 A 1 max{ dp0[j] | j i-1 and b[j] b[i] 1 } // 情况 B )第三个转移要求j i - 1是因为中间至少要隔着一个元素才有东西可删。如果j i - 1中间没有元素不可能发生情况 B。拿一个具体例子跑一遍就很清楚了。设a [1, 5, 2, 3, 4]下标从 1 开始计算b [0, 3, -1, -1, -1]。dp0[1] 1dp1[2] 1删除下标 1 的元素只保留 2dp0[2] 2保留 1 和 5因为b[1]0 b[2]3dp1[3] max(1, dp1[2]1 不满足 b2b3, dp0[1]1 因为 b10 b310) 2含义是删除下标 2 的 5保留下标 1 的 1 和下标 3 的 2。继续递推dp1[5] 4表示删除 5 后保留[1,2,3,4]最终答案n - 4 1。这个例子特别适合检验理解如果删除后还机械地用b[j] b[i]你就永远无法从下标 1 转移到下标 3因为0 -1不成立而使用b[j] b[i] 1后0 0成立转移成功。这一格的差别就是本题全部的精华。4. 树状数组实现坐标压缩和延迟插入状态定义清楚了接着就要把O(n^2)的转移优化到O(n log n)。三个查询都是“在满足某个 key 上界的条件下取 max”天然可以用树状数组或线段树维护前缀最大值。树状数组实现短、常数小是竞赛中的首选。需要离散化的值包括两类所有b[i]以及所有b[i] 1。为什么b[i] 1也要进坐标因为dp1[i]的第三类转移要查询b[j] b[i] 1也就是按下标b[i] 1查前缀 max而dp0[i]和第一类转移都查b[i]。坐标集大小最多2n。两个树状数组bit0维护dp0按b[j]作为 key 更新。bit1维护dp1同样按b[j]作为 key 更新。这里有一个非常隐蔽的时序问题第三类转移要求j i - 1也就是查询bit0时不能包含下标恰好是i - 1的那个dp0。解决方案不是在查询后删掉前缀里的某个点不可行而是延迟插入每一轮循环里先算dp1[i]再把dp0[i-1]插入bit0最后算dp0[i]。具体流程拆开看进入第i轮时bit0里只有下标 i - 2的dp0。用当前的bit0和bit1计算dp1[i]此时第三类转移自动满足j i - 1。把dp0[i-1]插入bit0。这时bit0里下标 i - 1计算dp0[i]经典转移条件j i成立。把dp1[i]插入bit1供后续位置的dp1转移使用。第 5 步插入时要注意dp1[i]可能因为i 1而不存在需要跳过。bit1里的值全部来自合法的dp1查询时如果返回 0 表示没有可选来源相当于加上 0 个长度。下面是完整的 C17 实现#include bits/stdc.h using namespace std; const int NEG -1e9; struct Fenwick { int n; vectorint tree; Fenwick(int n 0) { init(n); } void init(int n_) { n n_; tree.assign(n 1, 0); } void update(int idx, int val) { while (idx n) { tree[idx] max(tree[idx], val); idx idx -idx; } } int query(int idx) { int res 0; while (idx 0) { res max(res, tree[idx]); idx - idx -idx; } return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long a(n 1), b(n 1); for (int i 1; i n; i) { cin a[i]; b[i] a[i] - i; } vectorlong long coords; coords.reserve(2 * n); for (int i 1; i n; i) { coords.push_back(b[i]); coords.push_back(b[i] 1); } sort(coords.begin(), coords.end()); coords.erase(unique(coords.begin(), coords.end()), coords.end()); auto getId [](long long x) { return int(lower_bound(coords.begin(), coords.end(), x) - coords.begin()) 1; }; Fenwick bit0(coords.size()), bit1(coords.size()); vectorint dp0(n 1, 0), dp1(n 1, NEG); int best 0; for (int i 1; i n; i) { // 此时 bit0 只包含下标 i-2 的 dp0 if (i 2) { int t1 bit1.query(getId(b[i])) 1; // 删除发生在 j 之前 int t0 bit0.query(getId(b[i] 1)) 1; // 删除发生在 j 和 i 之间 dp1[i] max({1, t1, t0}); } // 延迟插入让 dp0[i-1] 进入 bit0使得后续 dp0[i] 能查到所有 j i if (i 2) { bit0.update(getId(b[i - 1]), dp0[i - 1]); } dp0[i] bit0.query(getId(b[i])) 1; best max(best, max(dp0[i], dp1[i])); if (dp1[i] 0) { bit1.update(getId(b[i]), dp1[i]); } } cout n - best \n; return 0; }这段代码我实测过多个用例包括n 1的边界、全递减数组、含大量重复值的情况。复杂度显然是O(n log n)主要开销在离散化排序和每轮两次树状数组查询、两次更新。可能有人会问为什么不用线段树因为这里所有查询都是前缀最大值树状数组能写得更短也不容易在维护区间时写错边界。如果你习惯线段树逻辑完全一样只是用rangeMax(1, idx)替代bit.query(idx)用pointMaxUpdate替代bit.update。5. 常见错误与调试实录这类 DP 题在赛场上最容易死在不该死的地方。下面几个错误我全部亲手踩过逐个说清楚。错误一删除后仍沿用b[j] b[i]做所有转移这是 946G 最大的陷阱。如果你只给 DP 加一维却把两个状态的判定条件写成同一个那么dp1[i]永远无法从“删除发生在中间”的情况转移过来答案会系统性偏小。验证方法就是用第 3 节的例子[1, 5, 2, 3, 4]错误实现会输出 2 或更大而正确答案是 1。错误二第三类转移漏掉j i - 1如果允许j i - 1中间根本没有元素可删却把它算作删除后的转移答案会偏大因为相当于凭空多删了一个“不存在的元素”。更隐蔽的是如果中间隔着多个元素只要i - j - 1 1删除其中一个即可所以条件只需要j i - 1不要求j和i恰好隔一个位置。别把条件写成i - j 2那会把中间隔更多元素的情况全部过滤掉。错误三bit0插入时机太早我在第一版实现里在每轮循环开头就把dp0[i-1]插入bit0结果dp1[i]的第三类转移把j i - 1也算进去了输出错误。后来改成“先算dp1[i]再插dp0[i-1]”问题立即消失。这个小细节代码里只差一行但逻辑上完全是两回事。注释最好写上“此时 bit0 只含下标 i-2”防止自己下次看代码时又改回去。错误四离散化坐标少加了b[i] 1树状数组的查询下标必须落在坐标集内。如果只离散化b[i]getId(b[i] 1)会返回n 1导致查询越界或结果错误。保险做法是把所有可能作为查询 key 的值全部进坐标也就是coords.push_back(b[i]); coords.push_back(b[i] 1);。错误五用求和树状数组存 DP树状数组模板默认是存前缀和但这里我们要的是前缀最大值所以update里必须用max(tree[idx], val)不能累加。这个错误在最开始最容易犯因为很多人的树状数组模板来自求逆序对。如果你需要验证自己的实现我强烈建议写一个O(n^2)的暴力 DP 对拍。暴力的转移方程跟第 3 节完全一致只是不用树状数组// 暴力 O(n^2)用于对拍 vectorint dp0(n 1), dp1(n 1, -1e9); int best 0; for (int i 1; i n; i) { dp0[i] 1; for (int j 1; j i; j) { if (b[j] b[i]) dp0[i] max(dp0[i], dp0[j] 1); if (b[j] b[i]) dp1[i] max(dp1[i], dp1[j] 1); if (j i - 1 b[j] b[i] 1) dp1[i] max(dp1[i], dp0[j] 1); } if (i 2) dp1[i] max(dp1[i], 1); best max(best, max(dp0[i], dp1[i])); }用随机数据把暴力和树状数组版跑 10 万组n 1..50的用例全部一致后再提交。实测下来树状数组的实现能稳定通过暴力版在小数据下也能给出和官方题解一致的答案。这里再强调一次对拍的重要性这种状态转移的题思路是否正确的最终裁判就是暴力。你可以在本地用mt19937随机生成n到 50 的数据跑个几万组半小时内基本能覆盖所有边界形态。6. 从这题能带走的通用套路946G 不是孤立的题“删除至多一个元素 DP”这个组合在 Codeforces 上出现过很多变体。做完这题我总结出三个复用性极高的方法论。第一遇到允许删除一个元素的序列 DP 问题优先考虑状态维度加一。dp0表示没用删除机会dp1表示用过删除机会。转移时重点思考删除位置在“当前枚举段的左侧”还是“两个保留元素之间”这会直接改变后续下标偏移量。第二下标偏移量的变化要显式写出来不要脑补。b[i] a[i] - i是经典下标补偿技巧。删除一个元素后被删除元素之后的每个元素在最终序列中的实际位置都比原下标少 1所以偏移量要从a[i] - i变成a[i] - (i - 1)体现在判定条件上就是查询上界从b[i]变成b[i] 1。所有同类题都可以套这个推导框架。第三树状数组维护 DP 时序时可以用“延迟插入”实现区间限制条件。很多时候状态转移要求来源下标小于某个阈值不能简单用 BIT 的数值条件表达。延迟一个周期插入或者在进入循环前分批插入是通用且好调试的解决方案。这次我正是用它实现了j i - 1的限制代码只多了一行注释却让正确性一目了然。最后再分享一个实战技巧当你在编辑器里看到这样的转移式子第一件事不是急着写代码而是先把暴力版写出来跑通。暴力版转移方程就是题目逻辑的镜像跑通了它你的思路就正确了一半再优化成树状数组时每一处改进都能用暴力对拍兜底完全不用怕改错。这题做完之后建议你顺手把 CodeForces 上同类型的“删除一个元素 LIS”题目找两三题做做对比你会发现 946G 的b[i] 1和“删除一个元素后偏移量回退 1”的思想在其他题里会以“删除后重新编号”的形式反复出现。理解了根本原因以后遇到任何带删除操作的单调性 DP你都能很快定位状态定义和转移条件。