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