CodeForces-946G 這題我第一眼看到名字以為是普通的 LIS 變種但真正寫起來才發(fā)現(xiàn)坑全藏在“刪除一個元素”這個看似微不足道的改動里。網(wǎng)上不少題解直接給了 DP 方程卻沒講清楚為什么偏移量會從b[i] a[i] - i變成b[i] 1導致很多人抄代碼都抄不明白。這篇文章把完整的推導鏈條補上附帶可直接 AC 的 C17 實現(xiàn)以及我用暴力對拍踩過的幾個典型錯誤希望能幫你在賽場上省下半小時。如果你已經(jīng)會經(jīng)典的最少修改次數(shù)問題n - LIS可以直接跳到第 3 節(jié)看刪除情況的處理如果還不熟悉我建議從頭讀因為后面的兩個偏移量判定實際上都建立在經(jīng)典做法之上。1. 先說結(jié)論這題到底在考什么題目大意非常簡潔給一個長度為n的數(shù)組你可以先刪除至多一個元素然后把任意位置的元素改成任意整數(shù)每次修改算一次操作目標是讓最終序列嚴格遞增求最小操作次數(shù)。數(shù)據(jù)范圍一般是n到2e5a[i]到1e9所以正解必須是O(n log n)。表面上看這就是經(jīng)典題“通過修改使數(shù)組嚴格遞增”加了一個刪除操作很多人第一反應(yīng)是枚舉刪除哪個位置然后對剩下的數(shù)組跑一遍n - LIS取最小值。這個思路復雜度是O(n^2 log n)直接超時而且它忽略了一個致命細節(jié)——刪除元素后剩余元素的相對下標發(fā)生了錯位經(jīng)典的a[i] - i偏移量不再統(tǒng)一適用。這題真正的考點就是如何把“刪除一個元素”造成的下標偏移用兩個狀態(tài)、兩組判定條件編碼進 DP 里。最終答案也很漂亮設(shè)best是允許刪除至多一個元素時能保留且不改動的最長遞增子序列長度則最小操作次數(shù)就是n - best。為什么這里的刪除操作沒額外算一次因為刪除本身算一次操作但刪除之后少了一個需要修改的元素刪除消耗和修改省下的次數(shù)正好抵消。這個結(jié)論在 dp 狀態(tài)里天然成立不需要單獨討論。2. 經(jīng)典版回顧為什么答案是 n - LIS先把沒有刪除操作的原版問題徹底吃透這是理解 946G 的地基。一個整數(shù)序列要嚴格遞增意味著對于任意保留位置i j必須滿足a[i] a[j]。由于元素都是整數(shù)更精確地說相鄰兩個保留元素之間至少要相差 1。如果這兩個保留元素在原數(shù)組中的下標距離是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是最少修改次數(shù)因為保留L個元素不動剩下n - L個元素都改掉總能找到合適的整數(shù)填補它們之間的空當。這里有一個容易誤會的點b數(shù)組求的是“非遞減”而不是“遞增”因為轉(zhuǎn)化后允許b[i] b[j]它對應(yīng)原數(shù)組中相鄰保留值恰好相差下標距離的情況。比如a [1, 2, 3]b [0, 0, 0]非遞減 LIS 長度為 3完全正確。如果用求嚴格遞增反而會得到 1那就錯了。從 LIS 的角度理解這件事也很直觀我們要挑選盡量多的原數(shù)組元素保持原值這些被挑選的元素本身必須能“塞進”一個嚴格遞增序列b[i] a[i] - i就是給每個元素扣掉它在新序列里應(yīng)該占的“位置租金”剩下的是它相對標準遞增軸的“富余量”。富余量非遞減才能保證沒有重疊或回退。經(jīng)典問題弄懂后再看允許刪除一個元素的情況你會發(fā)現(xiàn)在b的計算里每個保留元素應(yīng)該扣掉的下標取決于它前面實際刪除了幾個元素。3. 刪除一個元素后判定條件要分裂成兩個現(xiàn)在給經(jīng)典模型加一個刪除操作。設(shè)最終保留序列中的兩個相鄰保留位置在原數(shù)組中的下標為j和i且j i中間隔著i - j - 1個元素。古典情形下這中間的i - j - 1個元素全部通過修改保留在最終序列里所以空間要求是a[j] - j a[i] - i。現(xiàn)在允許刪除一個元素分兩種情況討論。情況 A刪除位置在j之前包括在保留序列第一個元素之前這時j和i之間沒有任何元素被刪除中間那些元素仍然全部需要修改填補。j和i都在“已刪除一個元素”這個事實之后它們的下標偏移都要加 1即應(yīng)該用b[i] 1和b[j] 1來比較。兩個偏移量同時加 1比較結(jié)果不變b[j] 1 b[i] 1 ? b[j] b[i]所以這種情況下保留條件跟經(jīng)典版完全一致b[j] b[i]。情況 B刪除位置發(fā)生在j和i之間這是本題的核心。中間原本有i - j - 1個元素現(xiàn)在被刪掉了一個只剩i - j - 2個元素需要修改后留在最終序列里。也就是說j和i在新序列中需要拉開的距離比經(jīng)典情況下少了 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原因就在這里——它不是拍腦袋而是嚴格推導出來的空間條件。根據(jù)這兩種情況我們定義兩個 DP 狀態(tài)dp0[i]以原數(shù)組第i個元素結(jié)尾沒有刪除任何元素時能保留的最大長度。dp1[i]以原數(shù)組第i個元素結(jié)尾已經(jīng)刪除過一個元素且刪除位置在i之前時能保留的最大長度。轉(zhuǎn)移方程如下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 )第三個轉(zhuǎn)移要求j i - 1是因為中間至少要隔著一個元素才有東西可刪。如果j i - 1中間沒有元素不可能發(fā)生情況 B。拿一個具體例子跑一遍就很清楚了。設(shè)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。繼續(xù)遞推dp1[5] 4表示刪除 5 后保留[1,2,3,4]最終答案n - 4 1。這個例子特別適合檢驗理解如果刪除后還機械地用b[j] b[i]你就永遠無法從下標 1 轉(zhuǎn)移到下標 3因為0 -1不成立而使用b[j] b[i] 1后0 0成立轉(zhuǎn)移成功。這一格的差別就是本題全部的精華。4. 樹狀數(shù)組實現(xiàn)坐標壓縮和延遲插入狀態(tài)定義清楚了接著就要把O(n^2)的轉(zhuǎn)移優(yōu)化到O(n log n)。三個查詢都是“在滿足某個 key 上界的條件下取 max”天然可以用樹狀數(shù)組或線段樹維護前綴最大值。樹狀數(shù)組實現(xiàn)短、常數(shù)小是競賽中的首選。需要離散化的值包括兩類所有b[i]以及所有b[i] 1。為什么b[i] 1也要進坐標因為dp1[i]的第三類轉(zhuǎn)移要查詢b[j] b[i] 1也就是按下標b[i] 1查前綴 max而dp0[i]和第一類轉(zhuǎn)移都查b[i]。坐標集大小最多2n。兩個樹狀數(shù)組bit0維護dp0按b[j]作為 key 更新。bit1維護dp1同樣按b[j]作為 key 更新。這里有一個非常隱蔽的時序問題第三類轉(zhuǎn)移要求j i - 1也就是查詢bit0時不能包含下標恰好是i - 1的那個dp0。解決方案不是在查詢后刪掉前綴里的某個點不可行而是延遲插入每一輪循環(huán)里先算dp1[i]再把dp0[i-1]插入bit0最后算dp0[i]。具體流程拆開看進入第i輪時bit0里只有下標 i - 2的dp0。用當前的bit0和bit1計算dp1[i]此時第三類轉(zhuǎn)移自動滿足j i - 1。把dp0[i-1]插入bit0。這時bit0里下標 i - 1計算dp0[i]經(jīng)典轉(zhuǎn)移條件j i成立。把dp1[i]插入bit1供后續(xù)位置的dp1轉(zhuǎn)移使用。第 5 步插入時要注意dp1[i]可能因為i 1而不存在需要跳過。bit1里的值全部來自合法的dp1查詢時如果返回 0 表示沒有可選來源相當于加上 0 個長度。下面是完整的 C17 實現(xiàn)#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; // 刪除發(fā)生在 j 之前 int t0 bit0.query(getId(b[i] 1)) 1; // 刪除發(fā)生在 j 和 i 之間 dp1[i] max({1, t1, t0}); } // 延遲插入讓 dp0[i-1] 進入 bit0使得后續(xù) 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的邊界、全遞減數(shù)組、含大量重復值的情況。復雜度顯然是O(n log n)主要開銷在離散化排序和每輪兩次樹狀數(shù)組查詢、兩次更新?？赡苡腥藭枮槭裁床挥镁€段樹因為這里所有查詢都是前綴最大值樹狀數(shù)組能寫得更短也不容易在維護區(qū)間時寫錯邊界。如果你習慣線段樹邏輯完全一樣只是用rangeMax(1, idx)替代bit.query(idx)用pointMaxUpdate替代bit.update。5. 常見錯誤與調(diào)試實錄這類 DP 題在賽場上最容易死在不該死的地方。下面幾個錯誤我全部親手踩過逐個說清楚。錯誤一刪除后仍沿用b[j] b[i]做所有轉(zhuǎn)移這是 946G 最大的陷阱。如果你只給 DP 加一維卻把兩個狀態(tài)的判定條件寫成同一個那么dp1[i]永遠無法從“刪除發(fā)生在中間”的情況轉(zhuǎn)移過來答案會系統(tǒng)性偏小。驗證方法就是用第 3 節(jié)的例子[1, 5, 2, 3, 4]錯誤實現(xiàn)會輸出 2 或更大而正確答案是 1。錯誤二第三類轉(zhuǎn)移漏掉j i - 1如果允許j i - 1中間根本沒有元素可刪卻把它算作刪除后的轉(zhuǎn)移答案會偏大因為相當于憑空多刪了一個“不存在的元素”。更隱蔽的是如果中間隔著多個元素只要i - j - 1 1刪除其中一個即可所以條件只需要j i - 1不要求j和i恰好隔一個位置。別把條件寫成i - j 2那會把中間隔更多元素的情況全部過濾掉。錯誤三bit0插入時機太早我在第一版實現(xiàn)里在每輪循環(huán)開頭就把dp0[i-1]插入bit0結(jié)果dp1[i]的第三類轉(zhuǎn)移把j i - 1也算進去了輸出錯誤。后來改成“先算dp1[i]再插dp0[i-1]”問題立即消失。這個小細節(jié)代碼里只差一行但邏輯上完全是兩回事。注釋最好寫上“此時 bit0 只含下標 i-2”防止自己下次看代碼時又改回去。錯誤四離散化坐標少加了b[i] 1樹狀數(shù)組的查詢下標必須落在坐標集內(nèi)。如果只離散化b[i]getId(b[i] 1)會返回n 1導致查詢越界或結(jié)果錯誤。保險做法是把所有可能作為查詢 key 的值全部進坐標也就是coords.push_back(b[i]); coords.push_back(b[i] 1);。錯誤五用求和樹狀數(shù)組存 DP樹狀數(shù)組模板默認是存前綴和但這里我們要的是前綴最大值所以update里必須用max(tree[idx], val)不能累加。這個錯誤在最開始最容易犯因為很多人的樹狀數(shù)組模板來自求逆序?qū)ΑＨ绻阈枰炞C自己的實現(xiàn)我強烈建議寫一個O(n^2)的暴力 DP 對拍。暴力的轉(zhuǎn)移方程跟第 3 節(jié)完全一致只是不用樹狀數(shù)組// 暴力 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])); }用隨機數(shù)據(jù)把暴力和樹狀數(shù)組版跑 10 萬組n 1..50的用例全部一致后再提交。實測下來樹狀數(shù)組的實現(xiàn)能穩(wěn)定通過暴力版在小數(shù)據(jù)下也能給出和官方題解一致的答案。這里再強調(diào)一次對拍的重要性這種狀態(tài)轉(zhuǎn)移的題思路是否正確的最終裁判就是暴力。你可以在本地用mt19937隨機生成n到 50 的數(shù)據(jù)跑個幾萬組半小時內(nèi)基本能覆蓋所有邊界形態(tài)。6. 從這題能帶走的通用套路946G 不是孤立的題“刪除至多一個元素 DP”這個組合在 Codeforces 上出現(xiàn)過很多變體。做完這題我總結(jié)出三個復用性極高的方法論。第一遇到允許刪除一個元素的序列 DP 問題優(yōu)先考慮狀態(tài)維度加一。dp0表示沒用刪除機會dp1表示用過刪除機會。轉(zhuǎn)移時重點思考刪除位置在“當前枚舉段的左側(cè)”還是“兩個保留元素之間”這會直接改變后續(xù)下標偏移量。第二下標偏移量的變化要顯式寫出來不要腦補。b[i] a[i] - i是經(jīng)典下標補償技巧。刪除一個元素后被刪除元素之后的每個元素在最終序列中的實際位置都比原下標少 1所以偏移量要從a[i] - i變成a[i] - (i - 1)體現(xiàn)在判定條件上就是查詢上界從b[i]變成b[i] 1。所有同類題都可以套這個推導框架。第三樹狀數(shù)組維護 DP 時序時可以用“延遲插入”實現(xiàn)區(qū)間限制條件。很多時候狀態(tài)轉(zhuǎn)移要求來源下標小于某個閾值不能簡單用 BIT 的數(shù)值條件表達。延遲一個周期插入或者在進入循環(huán)前分批插入是通用且好調(diào)試的解決方案。這次我正是用它實現(xiàn)了j i - 1的限制代碼只多了一行注釋卻讓正確性一目了然。最后再分享一個實戰(zhàn)技巧當你在編輯器里看到這樣的轉(zhuǎn)移式子第一件事不是急著寫代碼而是先把暴力版寫出來跑通。暴力版轉(zhuǎn)移方程就是題目邏輯的鏡像跑通了它你的思路就正確了一半再優(yōu)化成樹狀數(shù)組時每一處改進都能用暴力對拍兜底完全不用怕改錯。這題做完之后建議你順手把 CodeForces 上同類型的“刪除一個元素 LIS”題目找兩三題做做對比你會發(fā)現(xiàn) 946G 的b[i] 1和“刪除一個元素后偏移量回退 1”的思想在其他題里會以“刪除后重新編號”的形式反復出現(xiàn)。理解了根本原因以后遇到任何帶刪除操作的單調(diào)性 DP你都能很快定位狀態(tài)定義和轉(zhuǎn)移條件。