1. 考場(chǎng)初見(jiàn)這道題在整套七級(jí)卷子里是什么位置1.1 我的第一反應(yīng)2025年12月那場(chǎng)GESP C七級(jí)考試我做完選擇、判斷和前面幾道程序題后翻到程序設(shè)計(jì)大題第一眼看到學(xué)習(xí)小組這個(gè)題目時(shí)心里先松了一口氣——看起來(lái)不復(fù)雜。但讀完題面我在草稿紙上畫(huà)了快二十分鐘才意識(shí)到這是一道典型的序列切分型動(dòng)態(tài)規(guī)劃并且它同時(shí)牽涉排序、區(qū)間合法性判斷、區(qū)間最小值維護(hù)三個(gè)環(huán)節(jié)。考后和認(rèn)識(shí)的同學(xué)對(duì)答案至少有兩個(gè)人因?yàn)椴煌蛟谶@題上失分一個(gè)是上來(lái)就按從小到大貪心分組樣例過(guò)了大數(shù)據(jù)一跑就錯(cuò)另一個(gè)想到了用動(dòng)態(tài)規(guī)劃卻漏掉了每組人數(shù)不得少于 k 人的約束轉(zhuǎn)移方程寫(xiě)得半對(duì)半錯(cuò)。這篇復(fù)盤(pán)就把這道題的回憶版題意、完整推導(dǎo)過(guò)程和 C 題解整理出來(lái)。如果你計(jì)劃備考 2026 年 3 月或 6 月的 GESP 七級(jí)認(rèn)證這道題值得當(dāng)作備考樣板反復(fù)刷。1.2 它為什么能拉開(kāi)差距從 GESP 七級(jí)考綱來(lái)看重點(diǎn)覆蓋樹(shù)與圖的遍歷、最短路、最小生成樹(shù)、基礎(chǔ)動(dòng)態(tài)規(guī)劃、二分答案等方向。學(xué)習(xí)小組表面上是一個(gè)分組模擬題實(shí)際落點(diǎn)卻是動(dòng)態(tài)規(guī)劃而且是七級(jí)里很容易被輕視的分段 DP 方向。它不像樹(shù)形 DP 那樣有明顯遞歸結(jié)構(gòu)也不像背包那樣有固定模板很多人的第一反應(yīng)是能不能貪心這恰恰是題目設(shè)計(jì)得比較巧妙的地方樣例數(shù)據(jù)會(huì)引導(dǎo)你往貪心想但真正的數(shù)據(jù)范圍會(huì)告訴你貪心站不住腳。整套卷子做下來(lái)我的感受是這道題給的時(shí)間壓力不小前四十分鐘如果沉浸在圖論題里到這里就容易失去耐心?？梢坏┛创┧判蚝笄谐扇舾蛇B續(xù)段的本質(zhì)代碼量并不多。它考的不是背模板而是現(xiàn)場(chǎng)建模能力。下面我從回憶版題意說(shuō)起逐步給出推導(dǎo)和實(shí)現(xiàn)。2. 回憶版題意分組條件與輸入輸出格式2.1 記憶中的題面說(shuō)明一下GESP 官方不會(huì)在考后馬上釋放完整真題所以下面這份題面是根據(jù)同場(chǎng)考生的回憶和我的考場(chǎng)印象整理出來(lái)的復(fù)現(xiàn)版核心流程和考點(diǎn)保持原樣具體表述、樣例數(shù)值可能和官方卷面有差異。刷題時(shí)以這個(gè)復(fù)現(xiàn)版為準(zhǔn)思路是一致的。題目大意如下老師要把班里的 n 名學(xué)生分成若干個(gè)學(xué)習(xí)小組。每個(gè)學(xué)生有一個(gè)能力值 a[i]。老師規(guī)定每個(gè)小組至少有 k 名學(xué)生同一小組內(nèi)能力值最高和最低的學(xué)生差距不能超過(guò) d。求最少能分成多少個(gè)小組使得所有學(xué)生都恰好被分到某一個(gè)小組中。如果無(wú)法完成分組輸出 -1。輸入格式第一行三個(gè)整數(shù) n、k、d第二行 n 個(gè)整數(shù) a[1..n]。輸出格式一個(gè)整數(shù)表示最少小組數(shù)若無(wú)法分組則輸出 -1。2.2 數(shù)據(jù)范圍與時(shí)間限制雖然官方卷面給出的數(shù)據(jù)范圍我記不太準(zhǔn)確但按七級(jí)程序設(shè)計(jì)題的通常強(qiáng)度大致可以按以下范圍來(lái)約束參數(shù)取值說(shuō)明n1 ~ 2×10^5學(xué)生人數(shù)規(guī)模要到 O(n log n) 以內(nèi)k1 ~ n每組最少人數(shù)d0 ~ 10^9能力差距上限a[i]0 ~ 10^9能力值記得用 long long 讀這個(gè)數(shù)據(jù)范圍直接排除了 O(n^2) 的暴力分組方案。也就是說(shuō)正確解法的排序部分應(yīng)該是 O(n log n)分組計(jì)算部分至少要壓到 O(n log n)最好是 O(n)。2.3 考點(diǎn)定位我在考場(chǎng)上把它定位成三個(gè)步驟的疊加排序先按能力值升序排序連續(xù)段建模把任意分組轉(zhuǎn)化為把排序后的數(shù)組切成若干連續(xù)段動(dòng)態(tài)規(guī)劃求最少段數(shù)每段需要滿足長(zhǎng)度 ≥ k且首尾能力差 ≤ d。這個(gè)定位過(guò)程就是解這道題的核心下面一節(jié)詳細(xì)展開(kāi)。3. 解題的第一步為什么排序之后分組只可能是連續(xù)段3.1 交換論證先排序再切分一定不虧很多同學(xué)看到分組兩個(gè)字第一反應(yīng)是組合數(shù)爆炸n 個(gè)學(xué)生任意分組方案數(shù)根本枚舉不完。但題目里組內(nèi)能力極差不能超過(guò) d這個(gè)條件給了強(qiáng)結(jié)構(gòu)。先說(shuō)結(jié)論一定存在一個(gè)最優(yōu)解使得每個(gè)小組在按能力值升序排序之后都是數(shù)組里的一段連續(xù)區(qū)間。換句話說(shuō)不需要考慮跨段取人的分組。為什么可以用一個(gè)非常樸素的交換論證來(lái)解釋。假設(shè)排序后的數(shù)組是 b[1] ≤ b[2] ≤ ... ≤ b[n]。任意取一個(gè)最優(yōu)分組方案把某個(gè)小組的學(xué)生下標(biāo)標(biāo)出來(lái)。如果這個(gè)小組中有兩個(gè)學(xué)生 b[x] 和 b[y]而且 x y同時(shí)他們之間漏掉了一個(gè)下標(biāo) zx z y而這個(gè) b[z] 被分到了其他組那么我就可以把 b[z] 拿進(jìn)這個(gè)小組再?gòu)漠?dāng)前小組里挑一個(gè)與它交換的成員送出去。因?yàn)閿?shù)組是升序的把中間值放回當(dāng)前組的極差約束時(shí)組內(nèi) max 不會(huì)變大min 不會(huì)變小所以極差只會(huì)更小而被換出去的那個(gè)學(xué)生到另一個(gè)組里也不一定破壞約束因?yàn)樗哪芰χ嫡锰幵趦蓚€(gè)值的中間地帶屬于兩頭都套得上的位置。反復(fù)進(jìn)行這種交換最終所有小組的成員下標(biāo)都會(huì)變成連續(xù)區(qū)間。用生活類比就像排隊(duì)取餐能力值從小到大排列如果一組人里面夾著另一個(gè)組的人那這兩組的成員范圍必然交錯(cuò)。既然約束只關(guān)心區(qū)間內(nèi)的最大最小差距那么把夾在中間的人歸到同一組只會(huì)有利于滿足極差限制。這個(gè)結(jié)論是整個(gè)解法的地基。3.2 貪心行不行反例說(shuō)明貪心為什么錯(cuò)排序后切連續(xù)段這個(gè)結(jié)論一出最容易想到的就是貪心從左往右掃遇到能成一組就切一組。有經(jīng)驗(yàn)的選手會(huì)立刻警惕因?yàn)榍蟹珠L(zhǎng)度還要受到至少 k 人的約束這往往就是貪心失靈的地方。看一個(gè)反例n9k2d3 a [1, 2, 3, 4, 5, 6, 7, 8, 9]如果貪心每段盡量短就會(huì)切成 [1,2]、[3,4]、[5,6]、[7,8]最后剩下一個(gè) 9長(zhǎng)度不足 k直接認(rèn)為無(wú)解輸出 -1。但實(shí)際上 [1,2,3]、[4,5,6]、[7,8,9] 就是合法且最優(yōu)的 3 組。所以最短合法段貪心是錯(cuò)的。那每段盡量長(zhǎng)呢這個(gè)例子用最長(zhǎng)段貪心恰好能得到 3 組看起來(lái)可行但很容易構(gòu)造反例。比如n7k3d4 a [1, 2, 5, 6, 9, 10, 13]最長(zhǎng)段貪心從 1 開(kāi)始取1 到 5 極差 4滿足但再往后加 6 極差變成 5于是切出 [1,2,5]剩下 [6,9,10,13]從 6 開(kāi)始最長(zhǎng)能取到 9極差 3切 [6,9]最后剩 [10,13] 長(zhǎng)度只有 2不夠 3輸出無(wú)解。但手動(dòng)看[1,2,5]、[6,9,10,13] 這段極差是 7不行改成 [1,2,5,6] 極差 5也不行實(shí)際上這個(gè)數(shù)據(jù)在 k3、d4 下真的無(wú)解所以這個(gè)反例不夠有力。我需要強(qiáng)調(diào)最長(zhǎng)段貪心不是錯(cuò)誤在無(wú)解上而是錯(cuò)誤在少數(shù)情況下能把人分完但分的組數(shù)不一定最少。不過(guò)為了行文嚴(yán)謹(jǐn)我建議反問(wèn)一句——就算最長(zhǎng)段貪心碰巧能把人分完你能證明它得到的組數(shù)一定最少嗎如果不能考試時(shí)就不該拿沒(méi)證明的貪心去賭。這也是為什么正確做法必須退回到動(dòng)態(tài)規(guī)劃用一個(gè)可以嚴(yán)格證明的狀態(tài)轉(zhuǎn)移把所有切分方案都覆蓋到。4. 狀態(tài)設(shè)計(jì)與轉(zhuǎn)移方程序列切分DP的完整推導(dǎo)4.1 dp[i] 的定義和轉(zhuǎn)移式排序之后問(wèn)題變成給定升序數(shù)組 a[1..n]把它切成若干連續(xù)段每段長(zhǎng)度 ≥ k且每段首尾差值 ≤ d求最少段數(shù)。設(shè) dp[i] 表示把前 i 個(gè)學(xué)生即 a[1..i]全部完成分組所需的最少小組數(shù)。邊界條件是 dp[0]0表示前 0 個(gè)學(xué)生不需要分組。考慮最后一段是從第 j1 個(gè)學(xué)生到第 i 個(gè)學(xué)生那么顯然要滿足兩個(gè)條件段長(zhǎng)度至少為 ki - j ≥ k也就是 j ≤ i - k段內(nèi)極差不超過(guò) da[i] - a[j1] ≤ d也就是 a[j1] ≥ a[i] - d。于是轉(zhuǎn)移方程寫(xiě)出來(lái)就是dp[i] 1 min { dp[j] }其中 j 必須落在合法區(qū)間內(nèi)。這個(gè)合法區(qū)間的左右端點(diǎn)可以明確算出來(lái)。令 R i - k這是 j 的上界表示最后一段至少要留 k 個(gè)人。令 threshold a[i] - d這是最后一段第一位學(xué)生能力值的下限。由于數(shù)組升序我可以二分找到第一個(gè)大于等于 threshold 的位置 lb那么 j1 ≥ lb即 j ≥ lb - 1。同時(shí) j 不能小于 0所以左端點(diǎn) L max(0, lb - 1)。因此轉(zhuǎn)移區(qū)間就是j ∈ [ L, R ]只要 L ≤ R并且這個(gè)區(qū)間里存在一個(gè)可達(dá)的 dp 值dp[i] 就能由它更新過(guò)來(lái)。4.2 這個(gè)式子怎么高效求 min dp[j]暴力做法是每次枚舉 j復(fù)雜度 O(n^2)在 n2×10^5 下直接超時(shí)。需要優(yōu)化的點(diǎn)很明確左側(cè) L 和右側(cè) R 都隨 i 單調(diào)不減。R i - k 顯然隨 i 增大而增大threshold a[i] - d 因?yàn)閿?shù)組升序也隨 i 增大而增大所以 lower_bound 得到的 lb 不會(huì)往左移動(dòng)L 也不會(huì)減少。既然窗口兩端都是單調(diào)的就有兩條路可走方案數(shù)據(jù)結(jié)構(gòu)復(fù)雜度特點(diǎn)方案一線段樹(shù)維護(hù) dp 區(qū)間最小值O(n log n)思路直白容錯(cuò)高方案二單調(diào)隊(duì)列維護(hù)窗口內(nèi)最小 dpO(n)代碼短但要理解單調(diào)性我個(gè)人建議考場(chǎng)先寫(xiě)方案一確保不丟分有時(shí)間再優(yōu)化成方案二。下面兩版代碼都給出。4.3 為什么 j 區(qū)間 必須同時(shí)滿足兩個(gè)條件這里最容易漏掉的是很多選手會(huì)記得段長(zhǎng)條件 j ≤ i-k卻忘了還有極差條件。反過(guò)來(lái)也有選手只算極差忽略了段長(zhǎng)。這兩個(gè)條件任何一個(gè)不滿足轉(zhuǎn)移都是非法的。我從兩個(gè)角度檢查自己如果 j 太靠左說(shuō)明最后一段包括了很多學(xué)生段長(zhǎng)當(dāng)然足夠但極差可能爆掉a[i] - a[j1] d不滿足題意如果 j 太靠右說(shuō)明最后一段人太少可能不足 k 個(gè)也不合法。所以合法 j 必須落在左端點(diǎn) L 和右端點(diǎn) R的夾縫里。這個(gè)夾縫的推導(dǎo)既是本題的題眼也是我考場(chǎng)上想了最久的地方。5. C 題解線段樹(shù)版與單調(diào)隊(duì)列版5.1 先寫(xiě)一版不容易錯(cuò)的線段樹(shù)維護(hù)區(qū)間最小值線段樹(shù)版本思路最直接每次算出 L 和 R 后在線段樹(shù)上查詢區(qū)間 [L, R] 的 dp 最小值再用它更新 dp[i]并把 dp[i] 插入線段樹(shù)位置 i。這樣每一步都清清楚楚適合在考場(chǎng)上穩(wěn)扎穩(wěn)打。#include bits/stdc.h using namespace std; const int INF 1e9; vectorint seg; void update(int node, int l, int r, int pos, int val) { if (l r) { seg[node] val; return; } int mid (l r) 1; if (pos mid) update(node 1, l, mid, pos, val); else update(node 1 | 1, mid 1, r, pos, val); seg[node] min(seg[node 1], seg[node 1 | 1]); } int query(int node, int l, int r, int ql, int qr) { if (ql l r qr) return seg[node]; int mid (l r) 1; int res INF; if (ql mid) res min(res, query(node 1, l, mid, ql, qr)); if (qr mid) res min(res, query(node 1 | 1, mid 1, r, ql, qr)); return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; long long d; cin n k d; vectorlong long a(n 1); for (int i 1; i n; i) cin a[i]; sort(a.begin() 1, a.end()); seg.assign(4 * (n 1) 5, INF); vectorint dp(n 1, INF); dp[0] 0; update(1, 0, n, 0, 0); for (int i 1; i n; i) { int R i - k; if (R 0) continue; long long need a[i] - d; int lb lower_bound(a.begin() 1, a.begin() i 1, need) - a.begin(); int L max(0, lb - 1); if (L R) continue; int best query(1, 0, n, L, R); if (best INF) { dp[i] best 1; update(1, 0, n, i, dp[i]); } } cout (dp[n] INF ? -1 : dp[n]) \n; return 0; }這里有個(gè)細(xì)節(jié)lower_bound 的查找范圍我寫(xiě)的是a.begin() 1到a.begin() i 1而不是整個(gè)數(shù)組。原因很簡(jiǎn)單最后一段的起點(diǎn) j1 不可能大于 i所以只需要在前 i 個(gè)元素里找最小可行起點(diǎn)。寫(xiě)錯(cuò)成全局查找會(huì)把 j 算到 i 右邊導(dǎo)致非法轉(zhuǎn)移。5.2 更進(jìn)一步滑動(dòng)窗口單調(diào)隊(duì)列 O(n) 寫(xiě)法線段樹(shù)雖然穩(wěn)但代碼量稍大。如果對(duì)滑動(dòng)窗口足夠熟可以用單調(diào)隊(duì)列把 DP 部分壓到 O(n)。核心思想是維護(hù)當(dāng)前窗口 [L, R] 內(nèi)所有可行 j 的 dp 值隊(duì)頭永遠(yuǎn)是窗口內(nèi) dp 值最小的那個(gè)。#include bits/stdc.h using namespace std; const int INF 1e9; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; long long d; cin n k d; vectorlong long a(n 1); for (int i 1; i n; i) cin a[i]; sort(a.begin() 1, a.end()); vectorint dp(n 1, INF); dp[0] 0; dequeint q; // 存下標(biāo) j保證隊(duì)頭 dp 值最小 for (int i 1; i n; i) { int R i - k; if (R 0 dp[R] INF) { while (!q.empty() dp[q.back()] dp[R]) q.pop_back(); q.push_back(R); } long long need a[i] - d; int lb lower_bound(a.begin() 1, a.begin() i 1, need) - a.begin(); int L max(0, lb - 1); while (!q.empty() q.front() L) q.pop_front(); while (!q.empty() q.front() R) q.pop_front(); if (!q.empty()) dp[i] dp[q.front()] 1; } cout (dp[n] INF ? -1 : dp[n]) \n; return 0; }為什么可以這樣滑動(dòng)因?yàn)槊枯?i 增大時(shí)新進(jìn)入窗口的 j 只有 Ri-k 這一個(gè)而且 R 是單調(diào)增加的窗口左端點(diǎn) L 也單調(diào)不減。所以所有元素入隊(duì)一次、出隊(duì)一次總復(fù)雜度 O(n)。排序是 O(n log n)整體瓶頸就在排序上。注意入隊(duì)時(shí)dp[R] INF的判斷不能省如果 R 本身不可達(dá)把 INF 塞進(jìn)單調(diào)隊(duì)列會(huì)污染隊(duì)尾單調(diào)性后面可能把真實(shí)的最小 dp 彈掉。5.3 用一個(gè)完整例子手動(dòng)跑一遍拿前面的例子來(lái)驗(yàn)證n9k2d3a[1,2,3,4,5,6,7,8,9]。i1R-1跳過(guò)dp[1] 保持 INF即前 1 個(gè)人無(wú)法單獨(dú)成組i2R0dp[0]0 入隊(duì)need-2lb1L0隊(duì)列里有 0dp[2]1表示前 2 個(gè)人分成 1 組i3R1dp[1]INF不入隊(duì)need0lb1L0隊(duì)列里仍有 0dp[3]1表示前 3 個(gè)人 [1,2,3] 可以成 1 組i4R2dp[2]1 入隊(duì)need1lb1L0隊(duì)列中 dp[0]0 最小dp[4]1表示前 4 個(gè)人 [1,2,3,4] 極差 31 組就能覆蓋i5R3dp[3]1 入隊(duì)need2lb2a[2]2L1彈出下標(biāo) 0剩余下標(biāo) dp 最小為 1dp[5]2即前 5 個(gè)人至少要 2 組i9R7dp[7]2 入隊(duì)need6lb6L5窗口中 dp 最小為 2dp[9]3。最終輸出 3和手動(dòng)最優(yōu)方案一致。6. 邊界數(shù)據(jù)、易錯(cuò)點(diǎn)與考場(chǎng)經(jīng)驗(yàn)6.1 最容易翻車的四個(gè)地方第一k1 的邊界。k1 表示每組至少一個(gè)人這時(shí)候所有人都可以被各自分成一組但如果能力極差也滿足最好當(dāng)然是全部一人一組還是合并成一組顯然合并更優(yōu)所以 dp 應(yīng)該找到跨度更大的合法段。代碼里 Ri-1每次新加入的 j 是 i-1滑動(dòng)窗口邏輯不變?？紙?chǎng)最容易在這里栽的是想當(dāng)然認(rèn)為每組至少 1 人就是無(wú)腦分成 n 組忽略最少小組數(shù)的要求。第二d0 的情況。d0 意味著同一組內(nèi)所有人能力值必須完全相同。排序后要切連續(xù)段每個(gè)段內(nèi)部的數(shù)值都一樣。這種情況 data 中可能存在大量相同值lower_bound 找到的 lb 是第一個(gè)等于當(dāng)前值的位置不會(huì)有問(wèn)題但要注意如果某個(gè)值的數(shù)量少于 k必然無(wú)解。手動(dòng)構(gòu)造一個(gè) n6, k3, d0, a[1,1,2,2,3,3]輸出就應(yīng)該是 -1。第三long long 溢出。n、k 是 int 級(jí)別但 a[i] 和 d 是 10^9 級(jí)別a[i] - d可能是負(fù)數(shù)也可能超過(guò) int 范圍。我見(jiàn)過(guò)有人用 int 存差值導(dǎo)致負(fù)數(shù)溢出判錯(cuò)。穩(wěn)妥做法是 a 數(shù)組、d、threshold 全部聲明 long long。第四lower_bound 的終點(diǎn)寫(xiě)錯(cuò)。前面提過(guò)要限制在a.begin() i 1而不是整個(gè)數(shù)組。如果寫(xiě)全程查找當(dāng) a[i]-d 很小、lb 總是 1 時(shí)沒(méi)問(wèn)題但數(shù)據(jù)一旦讓 lb 超過(guò) i就會(huì)把 L 算到 R 右邊程序提前 continue導(dǎo)致本應(yīng)可分的方案被判成無(wú)解。6.2 考場(chǎng)上如何避坑我在考場(chǎng)上的習(xí)慣是動(dòng)態(tài)規(guī)劃題先寫(xiě)個(gè)小數(shù)據(jù)暴力驗(yàn)證思路。比如隨機(jī)生成長(zhǎng)度不超過(guò) 8 的數(shù)組把暴力的分組枚舉和 DP 結(jié)果對(duì)拍確認(rèn)轉(zhuǎn)移方程沒(méi)寫(xiě)歪。這個(gè)習(xí)慣救過(guò)我很多次學(xué)習(xí)小組這道題我在草稿紙上就是這么驗(yàn)的。另外如果時(shí)間只剩十五分鐘線段樹(shù)版本比單調(diào)隊(duì)列版本更值得寫(xiě)。因?yàn)榫€段樹(shù)的查詢邏輯一眼能看懂出錯(cuò)概率低單調(diào)隊(duì)列雖然代碼短但窗口邊界想不清楚反而容易寫(xiě)崩。GESP 七級(jí)拿分優(yōu)先不要為了炫技選風(fēng)險(xiǎn)更高的實(shí)現(xiàn)。7. 從學(xué)習(xí)小組延伸開(kāi)備考 GESP 七級(jí) DP 題的思路7.1 同類題目怎么遷移學(xué)習(xí)小組本質(zhì)上是一個(gè)一維數(shù)組連續(xù)分段 段約束的模型。這個(gè)模型在 GESP 七級(jí)里面非常常見(jiàn)換一層皮就可以變成很多題目把極差不超過(guò) d換成段內(nèi)所有數(shù)乘積不超過(guò)某個(gè)上限就是一類分段可行性題把最少組數(shù)換成最大組數(shù)狀態(tài)含義和轉(zhuǎn)移式都要調(diào)整但窗口維護(hù)的思路一致把一維數(shù)組換成樹(shù)上的路徑就是樹(shù)上 DP 的入門形態(tài)。所以我在備考時(shí)會(huì)把這類題歸成一個(gè)專題先排序再證明連續(xù)段性質(zhì)然后 dp[i] 表示前綴最優(yōu)解最后用單調(diào)隊(duì)列或線段樹(shù)優(yōu)化轉(zhuǎn)移。這個(gè)套路一套一個(gè)準(zhǔn)。7.2 我的個(gè)人體會(huì)這道題讓我最受用的是沒(méi)思路時(shí)先證明結(jié)構(gòu)性質(zhì)這個(gè)習(xí)慣。考場(chǎng)上很多人卡住是因?yàn)橐恢痹谙朐趺捶纸M而不是先問(wèn)最優(yōu)分組可能長(zhǎng)什么樣。一旦證明最優(yōu)解一定是排序后的連續(xù)段問(wèn)題難度立刻從指數(shù)級(jí)降到多項(xiàng)式級(jí)。如果你也在備考 GESP 七級(jí)我建議別只刷真題答案試著把每道題的結(jié)構(gòu)性質(zhì)寫(xiě)在題解第一行。比如學(xué)習(xí)小組的第一行就寫(xiě)排序后合法分組等價(jià)于把數(shù)組切成若干連續(xù)段每段滿足長(zhǎng)度 ≥ k 且首尾差 ≤ d。有這個(gè)性質(zhì)在后面 DP 只是按圖索驥。最后分享一個(gè)小技巧這種分段 DP 的題目寫(xiě)完代碼后一定補(bǔ)測(cè)全部學(xué)生能合成一組和完全無(wú)法分組兩個(gè)極端用例。前者用 d 很大的數(shù)據(jù)后者用 d0 且某些能力值人數(shù)少于 k 的數(shù)據(jù)。這兩個(gè)用例能同時(shí)檢驗(yàn)轉(zhuǎn)移方程和邊界條件我在實(shí)際比賽里靠這個(gè)習(xí)慣避免過(guò)不少無(wú)效提交。