橋杯國賽真題解析：拓?fù)渑判蚺c動(dòng)態(tài)規(guī)劃求解帶約束最長遞增子序列)
1. 項(xiàng)目概述從一道國賽真題看算法思維的深度最近在整理歷年藍(lán)橋杯的真題翻到了第十屆國賽JAVA B組的“遞增序列”這道題。說實(shí)話第一次看到題目描述時(shí)感覺它像是一道經(jīng)典的動(dòng)態(tài)規(guī)劃問題但仔細(xì)琢磨其輸入輸出格式和約束條件后發(fā)現(xiàn)它的內(nèi)核遠(yuǎn)比單純的“最長遞增子序列LIS”要精巧。這道題不僅考察了對基礎(chǔ)算法模型的掌握更考驗(yàn)選手在特定場景下對問題進(jìn)行抽象、轉(zhuǎn)化和優(yōu)化的綜合能力。它不像一些直白的搜索或模擬題其難點(diǎn)在于識別出題目給出的“序列”背后隱藏著一個(gè)經(jīng)典的圖論模型——拓?fù)渑判蚧蛘吒鼫?zhǔn)確地說是求解有向無環(huán)圖DAG的最長路徑。對于正在備賽藍(lán)橋杯尤其是目標(biāo)沖擊國賽的JAVA選手來說這類題目具有極高的研究價(jià)值。它完美地區(qū)分了“只會(huì)套模板”和“真正理解算法本質(zhì)”的選手。通過這道題我們可以深入探討幾個(gè)核心問題如何從問題描述中提取關(guān)鍵約束并建立數(shù)學(xué)模型當(dāng)經(jīng)典算法如LIS的O(nlogn)解法無法直接應(yīng)用時(shí)如何尋找突破口在JAVA實(shí)現(xiàn)中有哪些數(shù)據(jù)結(jié)構(gòu)能高效地支撐我們的算法邏輯以及面對看似復(fù)雜的條件如何設(shè)計(jì)清晰、健壯的代碼結(jié)構(gòu)接下來我將結(jié)合我的解題經(jīng)驗(yàn)徹底拆解這道題分享從問題分析、思路推導(dǎo)到代碼實(shí)現(xiàn)與調(diào)試的全過程并提供一些在競賽實(shí)戰(zhàn)中非常實(shí)用的技巧和避坑指南。2. 問題本質(zhì)與數(shù)學(xué)模型構(gòu)建2.1 題目核心需求解析首先我們需要拋開“遞增序列”這個(gè)字面名稱的干擾回歸題目本身的具體描述基于常見題型還原。題目通常會(huì)給出一個(gè)包含N個(gè)整數(shù)的序列A以及M組約束條件。每組約束條件形如(x, y)表示在最終要找的“遞增序列”中元素A[x]必須出現(xiàn)在元素A[y]之前即索引x處的值必須在索引y處的值前面。我們的目標(biāo)是找出滿足所有給定約束條件的、最長的遞增子序列的長度。這里的關(guān)鍵詞是“約束”。普通的LIS問題只關(guān)心數(shù)值的大小關(guān)系a[i] a[j]而本題額外增加了位置的前后關(guān)系約束。這直接導(dǎo)致我們無法直接使用經(jīng)典的LIS動(dòng)態(tài)規(guī)劃解法因?yàn)镈P狀態(tài)轉(zhuǎn)移方程dp[i] max(dp[j]) 1 (j i 且 a[j] a[i])只考慮了j在i之前但這里的“之前”僅指原序列中的下標(biāo)順序并未考慮我們額外添加的(x, y)約束?？赡艽嬖谥鴍 i但約束要求a[i]必須在a[j]之前的情況這就產(chǎn)生了矛盾。因此我們必須將這兩種關(guān)系統(tǒng)一起來。一個(gè)非常自然的想法是構(gòu)建一個(gè)有向圖。圖中的每個(gè)節(jié)點(diǎn)代表原序列中的一個(gè)位置或該位置的值。如果存在約束(x, y)則添加一條從節(jié)點(diǎn)x指向節(jié)點(diǎn)y的有向邊表示x必須排在y之前。同時(shí)數(shù)值本身的大小關(guān)系a[i] a[j]也是一種潛在的先后關(guān)系如果我們要將兩者都選入遞增序列那么值小的必須排在值大的前面。但這里需要注意數(shù)值關(guān)系不是強(qiáng)制約束它是一種可選的關(guān)系只有當(dāng)我們決定同時(shí)選取這兩個(gè)數(shù)時(shí)這個(gè)先后關(guān)系才需要被滿足。2.2 從約束到有向無環(huán)圖DAG的轉(zhuǎn)化上述分析引出了核心建模步驟我們最終需要找到一個(gè)節(jié)點(diǎn)的排列即子序列使得這個(gè)排列同時(shí)滿足兩類“先后”關(guān)系強(qiáng)制拓?fù)湫驅(qū)τ谒薪o定的(x, y)約束在排列中x必須出現(xiàn)在y之前。數(shù)值大小序?qū)τ谂帕兄腥我鈨蓚€(gè)不同的元素a[i]和a[j]如果a[i] a[j]那么在排列中i必須出現(xiàn)在j之前這是由“遞增”序列的定義決定的。為了讓問題可解我們需要將這兩種序合并。一個(gè)巧妙且正確的思路是利用強(qiáng)制拓?fù)湫騺怼皞鬟f”數(shù)值關(guān)系。具體來說我們首先根據(jù)M個(gè)約束條件構(gòu)建初始的有向圖。然后對于任意兩個(gè)節(jié)點(diǎn)i和ji ! j如果a[i] a[j]并且在原圖中存在從i到j(luò)的路徑即j在拓?fù)湫蛏弦蕾囉趇那么我們就添加一條從i到j(luò)的有向邊。為什么因?yàn)槿绻鹙依賴于ii必須在j前同時(shí)a[i] a[j]那么當(dāng)我們同時(shí)選擇i和j時(shí)i在j之前自然就滿足了數(shù)值遞增的要求。這條邊強(qiáng)化了它們之間的先后關(guān)系。然而這里有一個(gè)巨大的陷阱如果a[i] a[j]但原圖中存在從j到i的路徑即i依賴于j這就產(chǎn)生了矛盾。因?yàn)檫@意味著題目給出的約束要求i在j后面但數(shù)值關(guān)系要求i值小在j值大前面才能構(gòu)成遞增兩者無法同時(shí)滿足。在這種情況下節(jié)點(diǎn)i和j絕對不可能同時(shí)出現(xiàn)在任何一個(gè)合法的遞增序列中。在算法中我們需要檢測這種矛盾。一種方法是在嘗試添加數(shù)值關(guān)系邊之前先檢查兩個(gè)節(jié)點(diǎn)是否已經(jīng)在原約束下互斥即存在雙向路徑或形成了環(huán)。更普適的方法是在構(gòu)建完最終圖后檢查圖中是否存在環(huán)。如果存在環(huán)則說明約束存在矛盾可能無解但根據(jù)藍(lán)橋杯賽題特點(diǎn)通常數(shù)據(jù)保證有解。最終我們會(huì)得到一個(gè)擴(kuò)充后的有向圖G。這個(gè)圖G包含了所有必須遵守的先后順序。我們的目標(biāo)轉(zhuǎn)化為在圖G中尋找一條最長的路徑且路徑上節(jié)點(diǎn)的權(quán)值即原序列的a[i]是嚴(yán)格遞增的。由于數(shù)值遞增的要求已經(jīng)通過我們添加邊的策略僅當(dāng)a[i] a[j]且i能到達(dá)j時(shí)才加邊融入了圖中因此在這個(gè)新圖G中找一條最長路徑路徑上的節(jié)點(diǎn)自然滿足數(shù)值遞增。問題進(jìn)一步簡化為在DAG上求最長路徑。注意這里有一個(gè)極其關(guān)鍵的思維跳躍。為什么可以簡化成“DAG上的最長路徑”因?yàn)槲覀兲砑舆叺牟呗员ＷC了如果圖中有一條從u到v的邊那么一定有a[u] a[v]且 u 必須排在 v 之前。因此圖中的任意一條路徑其節(jié)點(diǎn)對應(yīng)的數(shù)值必然是遞增的并且滿足所有約束。所以找最長的滿足條件的遞增子序列等價(jià)于在這個(gè)DAG上找最長的路徑。這是一個(gè)非常經(jīng)典的模型轉(zhuǎn)化。2.3 算法選型與復(fù)雜度初估模型建立后算法選擇就清晰了圖構(gòu)建使用鄰接表存儲圖。首先添加M條約束邊。然后需要高效判斷任意兩點(diǎn)間是否存在路徑以決定是否添加數(shù)值關(guān)系邊。直接使用Floyd-Warshall求傳遞閉包是O(N^3)對于N可能達(dá)到10^3的數(shù)量級是不可接受的。通常競賽數(shù)據(jù)中M約束數(shù)不會(huì)極大我們可以采用拓?fù)渑判駼FS/DFS的方式為每個(gè)節(jié)點(diǎn)預(yù)處理出其可到達(dá)的節(jié)點(diǎn)集合。但這仍然是O(N*(NM))在N1000時(shí)可能處于臨界狀態(tài)需要謹(jǐn)慎實(shí)現(xiàn)。最長路徑求解在DAG上求最長路徑是標(biāo)準(zhǔn)拓?fù)渑判騽?dòng)態(tài)規(guī)劃。設(shè)dp[i]表示以節(jié)點(diǎn)i為終點(diǎn)的最長路徑長度。狀態(tài)轉(zhuǎn)移方程為dp[i] max(dp[j]) 1其中j是所有有邊指向i的節(jié)點(diǎn)。初始化dp[i] 1每個(gè)節(jié)點(diǎn)自身構(gòu)成長度為1的路徑。我們按照拓?fù)湫蛞来胃耫p值即可。整個(gè)算法的瓶頸在于圖的構(gòu)建階段尤其是處理數(shù)值關(guān)系邊。我們需要一個(gè)高效的“可達(dá)性判斷”方法。3. 核心實(shí)現(xiàn)細(xì)節(jié)與優(yōu)化策略3.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)與圖構(gòu)建在JAVA中我們?nèi)绾胃咝У乇硎緢D和進(jìn)行可達(dá)性判斷呢鄰接表存儲使用ArrayListArrayListInteger graph是最直觀的方式。但為了同時(shí)高效地進(jìn)行拓?fù)渑判蚝虳P我們還需要記錄每個(gè)節(jié)點(diǎn)的入度int[] inDegree?？蛇_(dá)性判斷優(yōu)化直接對每對(i, j)進(jìn)行DFS/BFS檢查是否可達(dá)復(fù)雜度太高。一個(gè)可行的優(yōu)化是利用位集BitSet來存儲每個(gè)節(jié)點(diǎn)的后繼集合。JAVA中的java.util.BitSet非常節(jié)省空間且位運(yùn)算速度快。我們創(chuàng)建一個(gè)BitSet[] reachable數(shù)組其中reachable[i]是一個(gè)BitSet表示從節(jié)點(diǎn)i出發(fā)可以到達(dá)哪些節(jié)點(diǎn)。首先根據(jù)M條約束邊構(gòu)建初始圖并通過記憶化DFS或拓?fù)渑判蚝筮f推的方式填充reachable數(shù)組。這是一個(gè)傳遞閉包的計(jì)算過程。對于DAG可以在拓?fù)淠嫘蛏线f推reachable[i].or(reachable[v])對于每個(gè)從i指向v的邊并且reachable[i].set(i)。然后遍歷所有節(jié)點(diǎn)對(i, j)如果a[i] a[j]且reachable[i].get(j)為真則在圖中添加一條從i到j(luò)的邊注意去重并更新inDegree[j]。同時(shí)如果a[i] a[j]但reachable[j].get(i)為真則說明i和j互相依賴但數(shù)值要求順序相反理論上它們不能共存。不過由于我們只添加i-j的邊如果j-i的路徑存在那么i和j就在同一個(gè)環(huán)里了嗎不一定但添加i-j邊后結(jié)合原有的j-i路徑就會(huì)形成環(huán)。因此更安全的做法是在添加邊后檢查圖中是否產(chǎn)生環(huán)?；蛘咴谔砑舆厱r(shí)直接判斷如果reachable[j].get(i)為真則跳過添加i-j這條邊因?yàn)橐延械募s束已經(jīng)要求j在i前這與數(shù)值關(guān)系沖突同時(shí)選擇它們會(huì)違反約束。構(gòu)建圖的具體步驟讀取N序列a[]M以及M條約束。初始化graphinDegreereachable(每個(gè)BitSet大小為N)。添加M條約束邊更新graph和inDegree。通過拓?fù)渑判蚧駾FS計(jì)算初始的reachable傳遞閉包。遍歷所有(i, j)如果i j跳過。如果a[i] a[j]跳過。如果reachable[i].get(j)為真說明已有路徑保證i在j前添加邊i-j如果尚未添加。如果reachable[j].get(i)為真說明約束要求j在i前這與a[i] a[j]沖突i和j不能同時(shí)被選入序列。對于本題求最長路徑我們的處理方式是不添加任何邊。因?yàn)樘砑尤魏芜叾紩?huì)導(dǎo)致環(huán)或邏輯矛盾。在最終的DAG中i和j之間將沒有邊相連最長路徑算法可能會(huì)選擇其中一個(gè)但不會(huì)同時(shí)選擇兩者這符合邏輯。重新初始化inDegree數(shù)組基于新圖計(jì)算。3.2 DAG最長路徑的動(dòng)態(tài)規(guī)劃求解在得到最終的DAG后求解最長路徑就是標(biāo)準(zhǔn)流程拓?fù)渑判蚴褂藐?duì)列將所有入度為0的節(jié)點(diǎn)入隊(duì)。依次出隊(duì)節(jié)點(diǎn)u將其加入拓?fù)湫蛄斜韙opoOrder并遍歷其所有鄰接點(diǎn)v將inDegree[v]--若減為0則入隊(duì)。動(dòng)態(tài)規(guī)劃初始化dp[]全為1。按照topoOrder的順序遍歷節(jié)點(diǎn)u對于u的每個(gè)后繼v執(zhí)行dp[v] Math.max(dp[v], dp[u] 1)。獲取答案遍歷所有節(jié)點(diǎn)的dp[i]最大值即為所求最長遞增且滿足約束子序列的長度。這個(gè)部分的代碼相對模板化但需要注意細(xì)節(jié)確保拓?fù)渑判蚰苷Ｍ瓿杉闯鲫?duì)節(jié)點(diǎn)數(shù)等于總節(jié)點(diǎn)數(shù)否則說明圖中有環(huán)這與題目假設(shè)可能不符但代碼中最好做異常處理。3.3 邊界條件與初始化心得在實(shí)際編碼中一些邊界條件容易忽略節(jié)點(diǎn)編號題目通常使用1-based索引而我們的代碼習(xí)慣使用0-based。需要在輸入輸出時(shí)進(jìn)行轉(zhuǎn)換內(nèi)部存儲統(tǒng)一用0-based避免混亂。去重邊在添加數(shù)值關(guān)系邊時(shí)同一條邊可能因?yàn)椴煌臄?shù)值對關(guān)系被多次嘗試添加。使用HashSet存儲每個(gè)節(jié)點(diǎn)的鄰接表或者在添加前檢查鄰接關(guān)系可以避免重復(fù)邊影響入度計(jì)算。BitSet內(nèi)存BitSet大小設(shè)為N。當(dāng)N很大時(shí)比如10^5BitSet數(shù)組的內(nèi)存占用約為N^2 / 8字節(jié)對于N1000大約是125KB可以接受但如果N達(dá)到10000就會(huì)約12.5MB可能超出內(nèi)存限制。這時(shí)就需要更精細(xì)的優(yōu)化例如只對必要的節(jié)點(diǎn)對進(jìn)行檢查或者采用分塊等策略。藍(lán)橋杯國賽B組的數(shù)據(jù)規(guī)模通常會(huì)控制在不必須使用極端優(yōu)化的情況下。序列值相等題目要求是“遞增”通常是嚴(yán)格遞增a[i] a[j]。如果出現(xiàn)相等值根據(jù)定義它們不能同時(shí)出現(xiàn)在遞增序列中。在我們的算法中對于a[i] a[j]的情況不會(huì)添加邊這是正確的。4. 代碼實(shí)現(xiàn)與逐行解析下面給出一個(gè)完整的JAVA實(shí)現(xiàn)并穿插關(guān)鍵注釋。假設(shè)輸入格式為第一行整數(shù)N第二行N個(gè)整數(shù)表示序列a第三行整數(shù)M接下來M行每行兩個(gè)整數(shù)x y1-based索引。import java.util.*; import java.io.*; public class Main { static int N; static int[] a; static ListListInteger graph; static int[] inDegree; static BitSet[] reachable; public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; // 1. 讀取輸入 N Integer.parseInt(br.readLine()); a new int[N]; st new StringTokenizer(br.readLine()); for (int i 0; i N; i) { a[i] Integer.parseInt(st.nextToken()); } int M Integer.parseInt(br.readLine()); // 初始化圖結(jié)構(gòu) graph new ArrayList(N); for (int i 0; i N; i) graph.add(new ArrayList()); inDegree new int[N]; reachable new BitSet[N]; for (int i 0; i N; i) reachable[i] new BitSet(N); // 2. 添加初始約束邊 for (int k 0; k M; k) { st new StringTokenizer(br.readLine()); int x Integer.parseInt(st.nextToken()) - 1; // 轉(zhuǎn)0-based int y Integer.parseInt(st.nextToken()) - 1; graph.get(x).add(y); inDegree[y]; reachable[x].set(y); // 直接后繼 } // 3. 計(jì)算初始傳遞閉包 (拓?fù)渑判蜻f推) calcReachable(); // 4. 根據(jù)數(shù)值關(guān)系添加新邊需要重建圖和入度 ListListInteger newGraph new ArrayList(N); for (int i 0; i N; i) newGraph.add(new ArrayList()); int[] newInDegree new int[N]; // 復(fù)制初始的約束邊 for (int u 0; u N; u) { for (int v : graph.get(u)) { newGraph.get(u).add(v); newInDegree[v]; } } // 添加數(shù)值關(guān)系邊 for (int i 0; i N; i) { for (int j 0; j N; j) { if (i j) continue; if (a[i] a[j]) { if (reachable[i].get(j)) { // i 能到 j添加邊 i-j newGraph.get(i).add(j); newInDegree[j]; } // 如果 reachable[j].get(i) 為真說明有沖突不添加邊 // 我們的算法中這種情況不會(huì)執(zhí)行添加操作符合邏輯 } } } // 5. 在新圖上進(jìn)行拓?fù)渑判蚯笞铋L路徑 graph newGraph; inDegree newInDegree; int ans longestPathInDAG(); System.out.println(ans); } // 計(jì)算傳遞閉包通過拓?fù)渑判虻哪嫘蜻f推 static void calcReachable() { // 拓?fù)渑判?int[] topo new int[N]; int[] indegCopy inDegree.clone(); QueueInteger q new LinkedList(); for (int i 0; i N; i) if (indegCopy[i] 0) q.offer(i); int idx 0; while (!q.isEmpty()) { int u q.poll(); topo[idx] u; for (int v : graph.get(u)) { if (--indegCopy[v] 0) q.offer(v); } } // 逆序遞推填充 reachable for (int i N - 1; i 0; i--) { int u topo[i]; reachable[u].set(u); // 自身可達(dá) for (int v : graph.get(u)) { reachable[u].or(reachable[v]); // u可達(dá)v并且可達(dá)v能到的所有點(diǎn) } } } // 在DAG上求最長路徑 static int longestPathInDAG() { int[] dp new int[N]; Arrays.fill(dp, 1); int[] indegCopy inDegree.clone(); QueueInteger q new LinkedList(); for (int i 0; i N; i) if (indegCopy[i] 0) q.offer(i); while (!q.isEmpty()) { int u q.poll(); for (int v : graph.get(u)) { dp[v] Math.max(dp[v], dp[u] 1); if (--indegCopy[v] 0) q.offer(v); } } int maxLen 0; for (int len : dp) maxLen Math.max(maxLen, len); return maxLen; } }關(guān)鍵代碼解析calcReachable()函數(shù)這是效率關(guān)鍵。我們首先進(jìn)行一次拓?fù)渑判虻玫酵負(fù)湫騮opo。然后逆序遍歷這個(gè)拓?fù)湫?。為什么逆序因?yàn)閷τ诠?jié)點(diǎn)u它的可達(dá)集合等于它所有直接后繼v的可達(dá)集合的并集再加上它自己。逆序保證了當(dāng)處理u時(shí)它的所有后繼v都已經(jīng)被處理過了reachable[v]已經(jīng)是完整的可以直接進(jìn)行or操作。添加數(shù)值關(guān)系邊的雙重循環(huán)這里復(fù)雜度是O(N^2)在N1000時(shí)是10^6可以接受。內(nèi)層判斷reachable[i].get(j)是O(1)的位操作極快。重建圖我們在添加新邊時(shí)創(chuàng)建了newGraph和newInDegree而不是在原圖上修改。這是因?yàn)樘砑舆吺窃隽窟^程直接在原圖上修改入度會(huì)干擾后續(xù)的邊添加判斷。全部確定后再替換是更清晰的做法。longestPathInDAG()函數(shù)標(biāo)準(zhǔn)的拓?fù)渑判駾P。dp[i]初始為1表示路徑至少包含自己。在松弛操作dp[v] Math.max(dp[v], dp[u] 1)中我們總是用更長的路徑來更新。5. 常見問題與調(diào)試技巧實(shí)錄即使思路清晰在實(shí)現(xiàn)這道題時(shí)依然會(huì)遇到不少坑。以下是我在調(diào)試和教學(xué)過程中總結(jié)的常見問題1. 超時(shí)問題癥狀程序在較大數(shù)據(jù)如N1000, M2000下運(yùn)行超時(shí)。排查首先檢查是否是O(N^3)的Floyd-Warshall求傳遞閉包。我們的calcReachable方法是O(N*(NM))在稀疏圖下接近O(N^2)。如果仍然超時(shí)可能是BitSet的or操作在N很大時(shí)開銷大。可以嘗試優(yōu)化只在reachable[i]和reachable[v]都是稀疏集時(shí)才有優(yōu)勢如果很稠密用boolean[][]數(shù)組可能更快但空間是O(N^2)。需要權(quán)衡。對于藍(lán)橋杯環(huán)境BitSet通常是夠用的。優(yōu)化技巧在添加數(shù)值關(guān)系邊的循環(huán)中可以做一些剪枝。例如如果a[i]已經(jīng)很大那么滿足a[i] a[j]的j可能不多?？梢允孪葘⒐?jié)點(diǎn)按值排序但會(huì)破壞索引關(guān)系實(shí)現(xiàn)復(fù)雜。一個(gè)簡單的優(yōu)化是內(nèi)層循環(huán)j可以從i1開始因?yàn)?i, j)和(j, i)會(huì)判斷兩次但我們的條件a[i] a[j]是不對稱的所以不能簡單減半。不過如果同時(shí)檢查reachable[i].get(j)和reachable[j].get(i)可以只遍歷ij的對。2. 答案錯(cuò)誤癥狀樣例通過但提交后部分測試點(diǎn)錯(cuò)誤。排查步驟檢查圖是否成環(huán)在longestPathInDAG中最后可以檢查一下出隊(duì)節(jié)點(diǎn)數(shù)量是否等于N。如果不等于說明新構(gòu)建的圖中有環(huán)這意味著我們的添加邊邏輯有誤可能產(chǎn)生了矛盾環(huán)。添加一段檢測代碼如果idx ! N輸出-1或進(jìn)行調(diào)試。驗(yàn)證傳遞閉包編寫一個(gè)小型測試打印出reachable數(shù)組看是否與手動(dòng)推導(dǎo)的一致。特別注意reachable[i].get(i)必須為真。檢查數(shù)值關(guān)系邊的添加條件最易錯(cuò)的點(diǎn)。必須確保只在a[i] a[j]且i能到達(dá)j的情況下添加i-j邊。如果a[i] a[j]但j能到達(dá)i則不能添加邊否則成環(huán)。如果兩者互不可達(dá)呢那么它們之間沒有約束可以任意排序但數(shù)值上a[i] a[j]如果我們想同時(shí)選它們必須保證i在j前。然而原圖沒有路徑我們能否添加一條邊來建立這個(gè)順序不能因?yàn)樘砑舆@條邊就人為增加了一個(gè)約束可能會(huì)影響其他節(jié)點(diǎn)。例如可能存在k有i-k和k-j的路徑但i不能直接到j(luò)。如果我們添加i-j就創(chuàng)建了一條捷徑可能使得一些原本不合法的路徑變得合法這里需要仔細(xì)思考。實(shí)際上正確的理解是如果i和j在原約束下無關(guān)即互不可達(dá)那么它們可以以任意順序出現(xiàn)在序列中。但是如果我們想同時(shí)選取它們構(gòu)成遞增就必須決定一個(gè)順序。這個(gè)順序的選擇會(huì)影響最終最長路徑。我們的算法選擇不添加邊意味著在最終的DAG中i和j之間沒有邊。那么最長路徑算法可能會(huì)選擇經(jīng)過i或經(jīng)過j的路徑但不會(huì)有一條路徑同時(shí)包含i和j因?yàn)閳D里沒有連接它們的邊。這可能會(huì)導(dǎo)致丟失最優(yōu)解。這是一個(gè)深坑修正方案對于互不可達(dá)的i, j且a[i] a[j]我們應(yīng)該添加邊嗎考慮一個(gè)簡單例子序列[1, 2]沒有約束。最長遞增子序列是[1, 2]。如果我們在構(gòu)建圖時(shí)因?yàn)?和2互不可達(dá)就不加邊那么最終圖是空的每個(gè)節(jié)點(diǎn)獨(dú)立最長路徑是1答案錯(cuò)誤。所以對于原圖中互不可達(dá)的節(jié)點(diǎn)數(shù)值關(guān)系應(yīng)該被考慮為一種可能的順序。但直接添加i-j邊是危險(xiǎn)的因?yàn)樗肓诵碌耐負(fù)潢P(guān)系可能會(huì)影響第三方節(jié)點(diǎn)。更安全的做法是不修改原圖而是在動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移時(shí)同時(shí)考慮數(shù)值關(guān)系和拓?fù)潢P(guān)系。但這會(huì)使DP變得復(fù)雜。3. 算法修正更準(zhǔn)確的模型與實(shí)現(xiàn)上述分析揭示了之前算法的缺陷。正確的做法應(yīng)該是最終的圖只包含題目給定的M條強(qiáng)制約束邊。數(shù)值關(guān)系不預(yù)先作為邊加入圖中而是在動(dòng)態(tài)規(guī)劃過程中作為轉(zhuǎn)移條件。重新定義狀態(tài)與轉(zhuǎn)移dp[i]表示以第i個(gè)元素結(jié)尾的、滿足所有約束的最長遞增子序列長度。轉(zhuǎn)移方程dp[i] max(dp[j] 1)其中j需要滿足兩個(gè)條件拓?fù)浼s束在原約束圖G中存在從j到i的路徑即j必須能到達(dá)i或者j和i在原圖中是無關(guān)的互不可達(dá)。簡單說就是不能存在從i到j(luò)的路徑否則i必須在j前矛盾。數(shù)值約束a[j] a[i]。這個(gè)轉(zhuǎn)移方程的正確性在于它保證了對于序列中任意相鄰的兩項(xiàng)它們既滿足數(shù)值遞增也滿足拓?fù)浼s束要么有路徑保證順序要么原本無約束可以自由排列。實(shí)現(xiàn)難點(diǎn)條件1的判斷需要在DP過程中頻繁進(jìn)行。我們可以預(yù)處理一個(gè)boolean[][] reachable矩陣或BitSet[]reachable[i][j]為真表示i能到達(dá)j。那么條件1就是!reachable[i][j]即i不能到達(dá)j。因?yàn)槿绻鹖能到達(dá)j那么i必須排在j前面而我們是以j結(jié)尾尋找前面的i這就不合法了。修正后的核心DP代碼static int solve() { // 預(yù)處理原約束圖的傳遞閉包 reachable calcReachable(); // 計(jì)算原圖的reachable graph是原約束圖 int[] dp new int[N]; Arrays.fill(dp, 1); int ans 1; // 按照某種順序進(jìn)行DP需要保證在計(jì)算dp[i]時(shí)所有可能的j都已經(jīng)計(jì)算過。 // 由于約束可能復(fù)雜簡單的從左到右遍歷不行。我們需要一個(gè)拓?fù)湫虻@里的拓?fù)湫蚴轻槍υs束圖的。 // 一個(gè)穩(wěn)妥的順序是先對原約束圖進(jìn)行拓?fù)渑判虬催@個(gè)順序DP。 int[] topoOrder getTopoOrderOfOriginalGraph(); for (int i : topoOrder) { for (int j 0; j N; j) { if (i j) continue; // 條件1: j 不能到達(dá) i (即 !reachable[j][i]) 否則j必須在i后面不能作為i的前驅(qū) // 條件2: a[j] a[i] if (!reachable[j][i] a[j] a[i]) { dp[i] Math.max(dp[i], dp[j] 1); } } ans Math.max(ans, dp[i]); } return ans; }注意這里reachable[j][i]為真表示j能到i即j必須排在i前面那么j就不能作為以i結(jié)尾的子序列中i的前一個(gè)元素因?yàn)轫樞蚍戳恕Ｋ晕覀冃枰氖?reachable[j][i]。同時(shí)我們還需要考慮j和i互不可達(dá)的情況這也是滿足條件的。這個(gè)算法的時(shí)間復(fù)雜度是O(N^2)對于N1000是可行的。它避免了構(gòu)建復(fù)雜的新圖邏輯更清晰直接。4. 內(nèi)存溢出使用boolean[N][N]存儲可達(dá)矩陣當(dāng)N5000時(shí)需要約25MB5000*5000/8/1024/1024 ≈ 23.8MB可能接近內(nèi)存限制。使用BitSet[N]可以節(jié)省約8倍空間。在藍(lán)橋杯環(huán)境中通常N在1000左右boolean[1000][1000]約1MB是安全的。調(diào)試心得從小樣例開始構(gòu)造N3,4的小數(shù)據(jù)包含各種情況有約束、無約束、數(shù)值相等、有環(huán)沖突手動(dòng)計(jì)算答案與程序輸出對比。打印中間狀態(tài)在關(guān)鍵步驟后如構(gòu)建完圖、計(jì)算完DP打印出圖的結(jié)構(gòu)、reachable矩陣、dp數(shù)組便于驗(yàn)證。理解矛盾情況如果題目數(shù)據(jù)可能無解我們的DP算法也能處理最終答案就是所有dp[i]的最大值至少為1。如果存在環(huán)原圖的拓?fù)渑判驎?huì)失敗可以在開始時(shí)檢測。6. 競賽實(shí)戰(zhàn)策略與總結(jié)回顧這道“遞增序列”它的難度在于將兩個(gè)不同維度的約束下標(biāo)拓?fù)湫蚝蛿?shù)值大小序融合到一個(gè)模型中。競賽中遇到此類問題可以遵循以下步驟問題轉(zhuǎn)化識別出強(qiáng)制約束題目給出的和弱約束問題定義隱含的如遞增。思考能否將弱約束轉(zhuǎn)化為在滿足強(qiáng)約束下的優(yōu)化目標(biāo)。圖論建模當(dāng)涉及“順序”、“前后”約束時(shí)優(yōu)先考慮有向圖。點(diǎn)代表元素邊代表順序關(guān)系。統(tǒng)一條件嘗試將兩種約束統(tǒng)一到同一個(gè)圖上。如果難以統(tǒng)一則考慮在動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移中同時(shí)檢查兩個(gè)條件如我們最終的修正算法。選擇算法在DAG上求最長路徑拓?fù)渑判駾P是標(biāo)準(zhǔn)做法。預(yù)處理傳遞閉包可達(dá)性矩陣是處理復(fù)雜前后關(guān)系判斷的常用技巧。復(fù)雜度分析估算數(shù)據(jù)規(guī)模N, M選擇合適的數(shù)據(jù)結(jié)構(gòu)鄰接表、BitSet。O(N^2)對于1000量級是安全的。代碼實(shí)現(xiàn)注意0-based和1-based轉(zhuǎn)換。使用清晰的變量名。將圖構(gòu)建、傳遞閉包計(jì)算、DP求解模塊化。測試與調(diào)試務(wù)必測試邊界情況N1M0所有a[i]相同約束形成鏈約束形成多個(gè)連通分量以及可能產(chǎn)生矛盾的情況。對于JAVA選手熟練使用ArrayList、Queue、BitSet、StringTokenizer用于快速輸入是基本功。在時(shí)間緊張的情況下可以準(zhǔn)備一些圖算法的模板代碼。這道題的價(jià)值在于它打破了“LIS必須用DP”的思維定式引入了拓?fù)浼s束將線性DP與圖論相結(jié)合。理解其本質(zhì)后可以舉一反三解決一類“帶約束的最優(yōu)序列”問題。例如有些問題約束是“某些元素不能相鄰”則可以轉(zhuǎn)化為圖上沒有邊相連約束是“某些元素必須間隔k個(gè)位置”則可以轉(zhuǎn)化為更復(fù)雜的圖模型。關(guān)鍵在于抽取約束的本質(zhì)并將其轉(zhuǎn)化為圖上的邊或動(dòng)態(tài)規(guī)劃的狀態(tài)限制。 藍(lán)橋杯國賽真題解析：拓?fù)渑判蚺c動(dòng)態(tài)規(guī)劃求解帶約束最長遞增子序列
1. 項(xiàng)目概述從一道國賽真題看算法思維的深度最近在整理歷年藍(lán)橋杯的真題翻到了第十屆國賽JAVA B組的“遞增序列”這道題。說實(shí)話第一次看到題目描述時(shí)感覺它像是一道經(jīng)典的動(dòng)態(tài)規(guī)劃問題但仔細(xì)琢磨其輸入輸出格式和約束條件后發(fā)現(xiàn)它的內(nèi)核遠(yuǎn)比單純的“最長遞增子序列LIS”要精巧。這道題不僅考察了對基礎(chǔ)算法模型的掌握更考驗(yàn)選手在特定場景下對問題進(jìn)行抽象、轉(zhuǎn)化和優(yōu)化的綜合能力。它不像一些直白的搜索或模擬題其難點(diǎn)在于識別出題目給出的“序列”背后隱藏著一個(gè)經(jīng)典的圖論模型——拓?fù)渑判蚧蛘吒鼫?zhǔn)確地說是求解有向無環(huán)圖DAG的最長路徑。對于正在備賽藍(lán)橋杯尤其是目標(biāo)沖擊國賽的JAVA選手來說這類題目具有極高的研究價(jià)值。它完美地區(qū)分了“只會(huì)套模板”和“真正理解算法本質(zhì)”的選手。通過這道題我們可以深入探討幾個(gè)核心問題如何從問題描述中提取關(guān)鍵約束并建立數(shù)學(xué)模型當(dāng)經(jīng)典算法如LIS的O(nlogn)解法無法直接應(yīng)用時(shí)如何尋找突破口在JAVA實(shí)現(xiàn)中有哪些數(shù)據(jù)結(jié)構(gòu)能高效地支撐我們的算法邏輯以及面對看似復(fù)雜的條件如何設(shè)計(jì)清晰、健壯的代碼結(jié)構(gòu)接下來我將結(jié)合我的解題經(jīng)驗(yàn)徹底拆解這道題分享從問題分析、思路推導(dǎo)到代碼實(shí)現(xiàn)與調(diào)試的全過程并提供一些在競賽實(shí)戰(zhàn)中非常實(shí)用的技巧和避坑指南。2. 問題本質(zhì)與數(shù)學(xué)模型構(gòu)建2.1 題目核心需求解析首先我們需要拋開“遞增序列”這個(gè)字面名稱的干擾回歸題目本身的具體描述基于常見題型還原。題目通常會(huì)給出一個(gè)包含N個(gè)整數(shù)的序列A以及M組約束條件。每組約束條件形如(x, y)表示在最終要找的“遞增序列”中元素A[x]必須出現(xiàn)在元素A[y]之前即索引x處的值必須在索引y處的值前面。我們的目標(biāo)是找出滿足所有給定約束條件的、最長的遞增子序列的長度。這里的關(guān)鍵詞是“約束”。普通的LIS問題只關(guān)心數(shù)值的大小關(guān)系a[i] a[j]而本題額外增加了位置的前后關(guān)系約束。這直接導(dǎo)致我們無法直接使用經(jīng)典的LIS動(dòng)態(tài)規(guī)劃解法因?yàn)镈P狀態(tài)轉(zhuǎn)移方程dp[i] max(dp[j]) 1 (j i 且 a[j] a[i])只考慮了j在i之前但這里的“之前”僅指原序列中的下標(biāo)順序并未考慮我們額外添加的(x, y)約束?？赡艽嬖谥鴍 i但約束要求a[i]必須在a[j]之前的情況這就產(chǎn)生了矛盾。因此我們必須將這兩種關(guān)系統(tǒng)一起來。一個(gè)非常自然的想法是構(gòu)建一個(gè)有向圖。圖中的每個(gè)節(jié)點(diǎn)代表原序列中的一個(gè)位置或該位置的值。如果存在約束(x, y)則添加一條從節(jié)點(diǎn)x指向節(jié)點(diǎn)y的有向邊表示x必須排在y之前。同時(shí)數(shù)值本身的大小關(guān)系a[i] a[j]也是一種潛在的先后關(guān)系如果我們要將兩者都選入遞增序列那么值小的必須排在值大的前面。但這里需要注意數(shù)值關(guān)系不是強(qiáng)制約束它是一種可選的關(guān)系只有當(dāng)我們決定同時(shí)選取這兩個(gè)數(shù)時(shí)這個(gè)先后關(guān)系才需要被滿足。2.2 從約束到有向無環(huán)圖DAG的轉(zhuǎn)化上述分析引出了核心建模步驟我們最終需要找到一個(gè)節(jié)點(diǎn)的排列即子序列使得這個(gè)排列同時(shí)滿足兩類“先后”關(guān)系強(qiáng)制拓?fù)湫驅(qū)τ谒薪o定的(x, y)約束在排列中x必須出現(xiàn)在y之前。數(shù)值大小序?qū)τ谂帕兄腥我鈨蓚€(gè)不同的元素a[i]和a[j]如果a[i] a[j]那么在排列中i必須出現(xiàn)在j之前這是由“遞增”序列的定義決定的。為了讓問題可解我們需要將這兩種序合并。一個(gè)巧妙且正確的思路是利用強(qiáng)制拓?fù)湫騺怼皞鬟f”數(shù)值關(guān)系。具體來說我們首先根據(jù)M個(gè)約束條件構(gòu)建初始的有向圖。然后對于任意兩個(gè)節(jié)點(diǎn)i和ji ! j如果a[i] a[j]并且在原圖中存在從i到j(luò)的路徑即j在拓?fù)湫蛏弦蕾囉趇那么我們就添加一條從i到j(luò)的有向邊。為什么因?yàn)槿绻鹙依賴于ii必須在j前同時(shí)a[i] a[j]那么當(dāng)我們同時(shí)選擇i和j時(shí)i在j之前自然就滿足了數(shù)值遞增的要求。這條邊強(qiáng)化了它們之間的先后關(guān)系。然而這里有一個(gè)巨大的陷阱如果a[i] a[j]但原圖中存在從j到i的路徑即i依賴于j這就產(chǎn)生了矛盾。因?yàn)檫@意味著題目給出的約束要求i在j后面但數(shù)值關(guān)系要求i值小在j值大前面才能構(gòu)成遞增兩者無法同時(shí)滿足。在這種情況下節(jié)點(diǎn)i和j絕對不可能同時(shí)出現(xiàn)在任何一個(gè)合法的遞增序列中。在算法中我們需要檢測這種矛盾。一種方法是在嘗試添加數(shù)值關(guān)系邊之前先檢查兩個(gè)節(jié)點(diǎn)是否已經(jīng)在原約束下互斥即存在雙向路徑或形成了環(huán)。更普適的方法是在構(gòu)建完最終圖后檢查圖中是否存在環(huán)。如果存在環(huán)則說明約束存在矛盾可能無解但根據(jù)藍(lán)橋杯賽題特點(diǎn)通常數(shù)據(jù)保證有解。最終我們會(huì)得到一個(gè)擴(kuò)充后的有向圖G。這個(gè)圖G包含了所有必須遵守的先后順序。我們的目標(biāo)轉(zhuǎn)化為在圖G中尋找一條最長的路徑且路徑上節(jié)點(diǎn)的權(quán)值即原序列的a[i]是嚴(yán)格遞增的。由于數(shù)值遞增的要求已經(jīng)通過我們添加邊的策略僅當(dāng)a[i] a[j]且i能到達(dá)j時(shí)才加邊融入了圖中因此在這個(gè)新圖G中找一條最長路徑路徑上的節(jié)點(diǎn)自然滿足數(shù)值遞增。問題進(jìn)一步簡化為在DAG上求最長路徑。注意這里有一個(gè)極其關(guān)鍵的思維跳躍。為什么可以簡化成“DAG上的最長路徑”因?yàn)槲覀兲砑舆叺牟呗员ＷC了如果圖中有一條從u到v的邊那么一定有a[u] a[v]且 u 必須排在 v 之前。因此圖中的任意一條路徑其節(jié)點(diǎn)對應(yīng)的數(shù)值必然是遞增的并且滿足所有約束。所以找最長的滿足條件的遞增子序列等價(jià)于在這個(gè)DAG上找最長的路徑。這是一個(gè)非常經(jīng)典的模型轉(zhuǎn)化。2.3 算法選型與復(fù)雜度初估模型建立后算法選擇就清晰了圖構(gòu)建使用鄰接表存儲圖。首先添加M條約束邊。然后需要高效判斷任意兩點(diǎn)間是否存在路徑以決定是否添加數(shù)值關(guān)系邊。直接使用Floyd-Warshall求傳遞閉包是O(N^3)對于N可能達(dá)到10^3的數(shù)量級是不可接受的。通常競賽數(shù)據(jù)中M約束數(shù)不會(huì)極大我們可以采用拓?fù)渑判駼FS/DFS的方式為每個(gè)節(jié)點(diǎn)預(yù)處理出其可到達(dá)的節(jié)點(diǎn)集合。但這仍然是O(N*(NM))在N1000時(shí)可能處于臨界狀態(tài)需要謹(jǐn)慎實(shí)現(xiàn)。最長路徑求解在DAG上求最長路徑是標(biāo)準(zhǔn)拓?fù)渑判騽?dòng)態(tài)規(guī)劃。設(shè)dp[i]表示以節(jié)點(diǎn)i為終點(diǎn)的最長路徑長度。狀態(tài)轉(zhuǎn)移方程為dp[i] max(dp[j]) 1其中j是所有有邊指向i的節(jié)點(diǎn)。初始化dp[i] 1每個(gè)節(jié)點(diǎn)自身構(gòu)成長度為1的路徑。我們按照拓?fù)湫蛞来胃耫p值即可。整個(gè)算法的瓶頸在于圖的構(gòu)建階段尤其是處理數(shù)值關(guān)系邊。我們需要一個(gè)高效的“可達(dá)性判斷”方法。3. 核心實(shí)現(xiàn)細(xì)節(jié)與優(yōu)化策略3.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)與圖構(gòu)建在JAVA中我們?nèi)绾胃咝У乇硎緢D和進(jìn)行可達(dá)性判斷呢鄰接表存儲使用ArrayListArrayListInteger graph是最直觀的方式。但為了同時(shí)高效地進(jìn)行拓?fù)渑判蚝虳P我們還需要記錄每個(gè)節(jié)點(diǎn)的入度int[] inDegree?？蛇_(dá)性判斷優(yōu)化直接對每對(i, j)進(jìn)行DFS/BFS檢查是否可達(dá)復(fù)雜度太高。一個(gè)可行的優(yōu)化是利用位集BitSet來存儲每個(gè)節(jié)點(diǎn)的后繼集合。JAVA中的java.util.BitSet非常節(jié)省空間且位運(yùn)算速度快。我們創(chuàng)建一個(gè)BitSet[] reachable數(shù)組其中reachable[i]是一個(gè)BitSet表示從節(jié)點(diǎn)i出發(fā)可以到達(dá)哪些節(jié)點(diǎn)。首先根據(jù)M條約束邊構(gòu)建初始圖并通過記憶化DFS或拓?fù)渑判蚝筮f推的方式填充reachable數(shù)組。這是一個(gè)傳遞閉包的計(jì)算過程。對于DAG可以在拓?fù)淠嫘蛏线f推reachable[i].or(reachable[v])對于每個(gè)從i指向v的邊并且reachable[i].set(i)。然后遍歷所有節(jié)點(diǎn)對(i, j)如果a[i] a[j]且reachable[i].get(j)為真則在圖中添加一條從i到j(luò)的邊注意去重并更新inDegree[j]。同時(shí)如果a[i] a[j]但reachable[j].get(i)為真則說明i和j互相依賴但數(shù)值要求順序相反理論上它們不能共存。不過由于我們只添加i-j的邊如果j-i的路徑存在那么i和j就在同一個(gè)環(huán)里了嗎不一定但添加i-j邊后結(jié)合原有的j-i路徑就會(huì)形成環(huán)。因此更安全的做法是在添加邊后檢查圖中是否產(chǎn)生環(huán)?；蛘咴谔砑舆厱r(shí)直接判斷如果reachable[j].get(i)為真則跳過添加i-j這條邊因?yàn)橐延械募s束已經(jīng)要求j在i前這與數(shù)值關(guān)系沖突同時(shí)選擇它們會(huì)違反約束。構(gòu)建圖的具體步驟讀取N序列a[]M以及M條約束。初始化graphinDegreereachable(每個(gè)BitSet大小為N)。添加M條約束邊更新graph和inDegree。通過拓?fù)渑判蚧駾FS計(jì)算初始的reachable傳遞閉包。遍歷所有(i, j)如果i j跳過。如果a[i] a[j]跳過。如果reachable[i].get(j)為真說明已有路徑保證i在j前添加邊i-j如果尚未添加。如果reachable[j].get(i)為真說明約束要求j在i前這與a[i] a[j]沖突i和j不能同時(shí)被選入序列。對于本題求最長路徑我們的處理方式是不添加任何邊。因?yàn)樘砑尤魏芜叾紩?huì)導(dǎo)致環(huán)或邏輯矛盾。在最終的DAG中i和j之間將沒有邊相連最長路徑算法可能會(huì)選擇其中一個(gè)但不會(huì)同時(shí)選擇兩者這符合邏輯。重新初始化inDegree數(shù)組基于新圖計(jì)算。3.2 DAG最長路徑的動(dòng)態(tài)規(guī)劃求解在得到最終的DAG后求解最長路徑就是標(biāo)準(zhǔn)流程拓?fù)渑判蚴褂藐?duì)列將所有入度為0的節(jié)點(diǎn)入隊(duì)。依次出隊(duì)節(jié)點(diǎn)u將其加入拓?fù)湫蛄斜韙opoOrder并遍歷其所有鄰接點(diǎn)v將inDegree[v]--若減為0則入隊(duì)。動(dòng)態(tài)規(guī)劃初始化dp[]全為1。按照topoOrder的順序遍歷節(jié)點(diǎn)u對于u的每個(gè)后繼v執(zhí)行dp[v] Math.max(dp[v], dp[u] 1)。獲取答案遍歷所有節(jié)點(diǎn)的dp[i]最大值即為所求最長遞增且滿足約束子序列的長度。這個(gè)部分的代碼相對模板化但需要注意細(xì)節(jié)確保拓?fù)渑判蚰苷Ｍ瓿杉闯鲫?duì)節(jié)點(diǎn)數(shù)等于總節(jié)點(diǎn)數(shù)否則說明圖中有環(huán)這與題目假設(shè)可能不符但代碼中最好做異常處理。3.3 邊界條件與初始化心得在實(shí)際編碼中一些邊界條件容易忽略節(jié)點(diǎn)編號題目通常使用1-based索引而我們的代碼習(xí)慣使用0-based。需要在輸入輸出時(shí)進(jìn)行轉(zhuǎn)換內(nèi)部存儲統(tǒng)一用0-based避免混亂。去重邊在添加數(shù)值關(guān)系邊時(shí)同一條邊可能因?yàn)椴煌臄?shù)值對關(guān)系被多次嘗試添加。使用HashSet存儲每個(gè)節(jié)點(diǎn)的鄰接表或者在添加前檢查鄰接關(guān)系可以避免重復(fù)邊影響入度計(jì)算。BitSet內(nèi)存BitSet大小設(shè)為N。當(dāng)N很大時(shí)比如10^5BitSet數(shù)組的內(nèi)存占用約為N^2 / 8字節(jié)對于N1000大約是125KB可以接受但如果N達(dá)到10000就會(huì)約12.5MB可能超出內(nèi)存限制。這時(shí)就需要更精細(xì)的優(yōu)化例如只對必要的節(jié)點(diǎn)對進(jìn)行檢查或者采用分塊等策略。藍(lán)橋杯國賽B組的數(shù)據(jù)規(guī)模通常會(huì)控制在不必須使用極端優(yōu)化的情況下。序列值相等題目要求是“遞增”通常是嚴(yán)格遞增a[i] a[j]。如果出現(xiàn)相等值根據(jù)定義它們不能同時(shí)出現(xiàn)在遞增序列中。在我們的算法中對于a[i] a[j]的情況不會(huì)添加邊這是正確的。4. 代碼實(shí)現(xiàn)與逐行解析下面給出一個(gè)完整的JAVA實(shí)現(xiàn)并穿插關(guān)鍵注釋。假設(shè)輸入格式為第一行整數(shù)N第二行N個(gè)整數(shù)表示序列a第三行整數(shù)M接下來M行每行兩個(gè)整數(shù)x y1-based索引。import java.util.*; import java.io.*; public class Main { static int N; static int[] a; static ListListInteger graph; static int[] inDegree; static BitSet[] reachable; public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; // 1. 讀取輸入 N Integer.parseInt(br.readLine()); a new int[N]; st new StringTokenizer(br.readLine()); for (int i 0; i N; i) { a[i] Integer.parseInt(st.nextToken()); } int M Integer.parseInt(br.readLine()); // 初始化圖結(jié)構(gòu) graph new ArrayList(N); for (int i 0; i N; i) graph.add(new ArrayList()); inDegree new int[N]; reachable new BitSet[N]; for (int i 0; i N; i) reachable[i] new BitSet(N); // 2. 添加初始約束邊 for (int k 0; k M; k) { st new StringTokenizer(br.readLine()); int x Integer.parseInt(st.nextToken()) - 1; // 轉(zhuǎn)0-based int y Integer.parseInt(st.nextToken()) - 1; graph.get(x).add(y); inDegree[y]; reachable[x].set(y); // 直接后繼 } // 3. 計(jì)算初始傳遞閉包 (拓?fù)渑判蜻f推) calcReachable(); // 4. 根據(jù)數(shù)值關(guān)系添加新邊需要重建圖和入度 ListListInteger newGraph new ArrayList(N); for (int i 0; i N; i) newGraph.add(new ArrayList()); int[] newInDegree new int[N]; // 復(fù)制初始的約束邊 for (int u 0; u N; u) { for (int v : graph.get(u)) { newGraph.get(u).add(v); newInDegree[v]; } } // 添加數(shù)值關(guān)系邊 for (int i 0; i N; i) { for (int j 0; j N; j) { if (i j) continue; if (a[i] a[j]) { if (reachable[i].get(j)) { // i 能到 j添加邊 i-j newGraph.get(i).add(j); newInDegree[j]; } // 如果 reachable[j].get(i) 為真說明有沖突不添加邊 // 我們的算法中這種情況不會(huì)執(zhí)行添加操作符合邏輯 } } } // 5. 在新圖上進(jìn)行拓?fù)渑判蚯笞铋L路徑 graph newGraph; inDegree newInDegree; int ans longestPathInDAG(); System.out.println(ans); } // 計(jì)算傳遞閉包通過拓?fù)渑判虻哪嫘蜻f推 static void calcReachable() { // 拓?fù)渑判?int[] topo new int[N]; int[] indegCopy inDegree.clone(); QueueInteger q new LinkedList(); for (int i 0; i N; i) if (indegCopy[i] 0) q.offer(i); int idx 0; while (!q.isEmpty()) { int u q.poll(); topo[idx] u; for (int v : graph.get(u)) { if (--indegCopy[v] 0) q.offer(v); } } // 逆序遞推填充 reachable for (int i N - 1; i 0; i--) { int u topo[i]; reachable[u].set(u); // 自身可達(dá) for (int v : graph.get(u)) { reachable[u].or(reachable[v]); // u可達(dá)v并且可達(dá)v能到的所有點(diǎn) } } } // 在DAG上求最長路徑 static int longestPathInDAG() { int[] dp new int[N]; Arrays.fill(dp, 1); int[] indegCopy inDegree.clone(); QueueInteger q new LinkedList(); for (int i 0; i N; i) if (indegCopy[i] 0) q.offer(i); while (!q.isEmpty()) { int u q.poll(); for (int v : graph.get(u)) { dp[v] Math.max(dp[v], dp[u] 1); if (--indegCopy[v] 0) q.offer(v); } } int maxLen 0; for (int len : dp) maxLen Math.max(maxLen, len); return maxLen; } }關(guān)鍵代碼解析calcReachable()函數(shù)這是效率關(guān)鍵。我們首先進(jìn)行一次拓?fù)渑判虻玫酵負(fù)湫騮opo。然后逆序遍歷這個(gè)拓?fù)湫?。為什么逆序因?yàn)閷τ诠?jié)點(diǎn)u它的可達(dá)集合等于它所有直接后繼v的可達(dá)集合的并集再加上它自己。逆序保證了當(dāng)處理u時(shí)它的所有后繼v都已經(jīng)被處理過了reachable[v]已經(jīng)是完整的可以直接進(jìn)行or操作。添加數(shù)值關(guān)系邊的雙重循環(huán)這里復(fù)雜度是O(N^2)在N1000時(shí)是10^6可以接受。內(nèi)層判斷reachable[i].get(j)是O(1)的位操作極快。重建圖我們在添加新邊時(shí)創(chuàng)建了newGraph和newInDegree而不是在原圖上修改。這是因?yàn)樘砑舆吺窃隽窟^程直接在原圖上修改入度會(huì)干擾后續(xù)的邊添加判斷。全部確定后再替換是更清晰的做法。longestPathInDAG()函數(shù)標(biāo)準(zhǔn)的拓?fù)渑判駾P。dp[i]初始為1表示路徑至少包含自己。在松弛操作dp[v] Math.max(dp[v], dp[u] 1)中我們總是用更長的路徑來更新。5. 常見問題與調(diào)試技巧實(shí)錄即使思路清晰在實(shí)現(xiàn)這道題時(shí)依然會(huì)遇到不少坑。以下是我在調(diào)試和教學(xué)過程中總結(jié)的常見問題1. 超時(shí)問題癥狀程序在較大數(shù)據(jù)如N1000, M2000下運(yùn)行超時(shí)。排查首先檢查是否是O(N^3)的Floyd-Warshall求傳遞閉包。我們的calcReachable方法是O(N*(NM))在稀疏圖下接近O(N^2)。如果仍然超時(shí)可能是BitSet的or操作在N很大時(shí)開銷大。可以嘗試優(yōu)化只在reachable[i]和reachable[v]都是稀疏集時(shí)才有優(yōu)勢如果很稠密用boolean[][]數(shù)組可能更快但空間是O(N^2)。需要權(quán)衡。對于藍(lán)橋杯環(huán)境BitSet通常是夠用的。優(yōu)化技巧在添加數(shù)值關(guān)系邊的循環(huán)中可以做一些剪枝。例如如果a[i]已經(jīng)很大那么滿足a[i] a[j]的j可能不多?？梢允孪葘⒐?jié)點(diǎn)按值排序但會(huì)破壞索引關(guān)系實(shí)現(xiàn)復(fù)雜。一個(gè)簡單的優(yōu)化是內(nèi)層循環(huán)j可以從i1開始因?yàn)?i, j)和(j, i)會(huì)判斷兩次但我們的條件a[i] a[j]是不對稱的所以不能簡單減半。不過如果同時(shí)檢查reachable[i].get(j)和reachable[j].get(i)可以只遍歷ij的對。2. 答案錯(cuò)誤癥狀樣例通過但提交后部分測試點(diǎn)錯(cuò)誤。排查步驟檢查圖是否成環(huán)在longestPathInDAG中最后可以檢查一下出隊(duì)節(jié)點(diǎn)數(shù)量是否等于N。如果不等于說明新構(gòu)建的圖中有環(huán)這意味著我們的添加邊邏輯有誤可能產(chǎn)生了矛盾環(huán)。添加一段檢測代碼如果idx ! N輸出-1或進(jìn)行調(diào)試。驗(yàn)證傳遞閉包編寫一個(gè)小型測試打印出reachable數(shù)組看是否與手動(dòng)推導(dǎo)的一致。特別注意reachable[i].get(i)必須為真。檢查數(shù)值關(guān)系邊的添加條件最易錯(cuò)的點(diǎn)。必須確保只在a[i] a[j]且i能到達(dá)j的情況下添加i-j邊。如果a[i] a[j]但j能到達(dá)i則不能添加邊否則成環(huán)。如果兩者互不可達(dá)呢那么它們之間沒有約束可以任意排序但數(shù)值上a[i] a[j]如果我們想同時(shí)選它們必須保證i在j前。然而原圖沒有路徑我們能否添加一條邊來建立這個(gè)順序不能因?yàn)樘砑舆@條邊就人為增加了一個(gè)約束可能會(huì)影響其他節(jié)點(diǎn)。例如可能存在k有i-k和k-j的路徑但i不能直接到j(luò)。如果我們添加i-j就創(chuàng)建了一條捷徑可能使得一些原本不合法的路徑變得合法這里需要仔細(xì)思考。實(shí)際上正確的理解是如果i和j在原約束下無關(guān)即互不可達(dá)那么它們可以以任意順序出現(xiàn)在序列中。但是如果我們想同時(shí)選取它們構(gòu)成遞增就必須決定一個(gè)順序。這個(gè)順序的選擇會(huì)影響最終最長路徑。我們的算法選擇不添加邊意味著在最終的DAG中i和j之間沒有邊。那么最長路徑算法可能會(huì)選擇經(jīng)過i或經(jīng)過j的路徑但不會(huì)有一條路徑同時(shí)包含i和j因?yàn)閳D里沒有連接它們的邊。這可能會(huì)導(dǎo)致丟失最優(yōu)解。這是一個(gè)深坑修正方案對于互不可達(dá)的i, j且a[i] a[j]我們應(yīng)該添加邊嗎考慮一個(gè)簡單例子序列[1, 2]沒有約束。最長遞增子序列是[1, 2]。如果我們在構(gòu)建圖時(shí)因?yàn)?和2互不可達(dá)就不加邊那么最終圖是空的每個(gè)節(jié)點(diǎn)獨(dú)立最長路徑是1答案錯(cuò)誤。所以對于原圖中互不可達(dá)的節(jié)點(diǎn)數(shù)值關(guān)系應(yīng)該被考慮為一種可能的順序。但直接添加i-j邊是危險(xiǎn)的因?yàn)樗肓诵碌耐負(fù)潢P(guān)系可能會(huì)影響第三方節(jié)點(diǎn)。更安全的做法是不修改原圖而是在動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移時(shí)同時(shí)考慮數(shù)值關(guān)系和拓?fù)潢P(guān)系。但這會(huì)使DP變得復(fù)雜。3. 算法修正更準(zhǔn)確的模型與實(shí)現(xiàn)上述分析揭示了之前算法的缺陷。正確的做法應(yīng)該是最終的圖只包含題目給定的M條強(qiáng)制約束邊。數(shù)值關(guān)系不預(yù)先作為邊加入圖中而是在動(dòng)態(tài)規(guī)劃過程中作為轉(zhuǎn)移條件。重新定義狀態(tài)與轉(zhuǎn)移dp[i]表示以第i個(gè)元素結(jié)尾的、滿足所有約束的最長遞增子序列長度。轉(zhuǎn)移方程dp[i] max(dp[j] 1)其中j需要滿足兩個(gè)條件拓?fù)浼s束在原約束圖G中存在從j到i的路徑即j必須能到達(dá)i或者j和i在原圖中是無關(guān)的互不可達(dá)。簡單說就是不能存在從i到j(luò)的路徑否則i必須在j前矛盾。數(shù)值約束a[j] a[i]。這個(gè)轉(zhuǎn)移方程的正確性在于它保證了對于序列中任意相鄰的兩項(xiàng)它們既滿足數(shù)值遞增也滿足拓?fù)浼s束要么有路徑保證順序要么原本無約束可以自由排列。實(shí)現(xiàn)難點(diǎn)條件1的判斷需要在DP過程中頻繁進(jìn)行。我們可以預(yù)處理一個(gè)boolean[][] reachable矩陣或BitSet[]reachable[i][j]為真表示i能到達(dá)j。那么條件1就是!reachable[i][j]即i不能到達(dá)j。因?yàn)槿绻鹖能到達(dá)j那么i必須排在j前面而我們是以j結(jié)尾尋找前面的i這就不合法了。修正后的核心DP代碼static int solve() { // 預(yù)處理原約束圖的傳遞閉包 reachable calcReachable(); // 計(jì)算原圖的reachable graph是原約束圖 int[] dp new int[N]; Arrays.fill(dp, 1); int ans 1; // 按照某種順序進(jìn)行DP需要保證在計(jì)算dp[i]時(shí)所有可能的j都已經(jīng)計(jì)算過。 // 由于約束可能復(fù)雜簡單的從左到右遍歷不行。我們需要一個(gè)拓?fù)湫虻@里的拓?fù)湫蚴轻槍υs束圖的。 // 一個(gè)穩(wěn)妥的順序是先對原約束圖進(jìn)行拓?fù)渑判虬催@個(gè)順序DP。 int[] topoOrder getTopoOrderOfOriginalGraph(); for (int i : topoOrder) { for (int j 0; j N; j) { if (i j) continue; // 條件1: j 不能到達(dá) i (即 !reachable[j][i]) 否則j必須在i后面不能作為i的前驅(qū) // 條件2: a[j] a[i] if (!reachable[j][i] a[j] a[i]) { dp[i] Math.max(dp[i], dp[j] 1); } } ans Math.max(ans, dp[i]); } return ans; }注意這里reachable[j][i]為真表示j能到i即j必須排在i前面那么j就不能作為以i結(jié)尾的子序列中i的前一個(gè)元素因?yàn)轫樞蚍戳恕Ｋ晕覀冃枰氖?reachable[j][i]。同時(shí)我們還需要考慮j和i互不可達(dá)的情況這也是滿足條件的。這個(gè)算法的時(shí)間復(fù)雜度是O(N^2)對于N1000是可行的。它避免了構(gòu)建復(fù)雜的新圖邏輯更清晰直接。4. 內(nèi)存溢出使用boolean[N][N]存儲可達(dá)矩陣當(dāng)N5000時(shí)需要約25MB5000*5000/8/1024/1024 ≈ 23.8MB可能接近內(nèi)存限制。使用BitSet[N]可以節(jié)省約8倍空間。在藍(lán)橋杯環(huán)境中通常N在1000左右boolean[1000][1000]約1MB是安全的。調(diào)試心得從小樣例開始構(gòu)造N3,4的小數(shù)據(jù)包含各種情況有約束、無約束、數(shù)值相等、有環(huán)沖突手動(dòng)計(jì)算答案與程序輸出對比。打印中間狀態(tài)在關(guān)鍵步驟后如構(gòu)建完圖、計(jì)算完DP打印出圖的結(jié)構(gòu)、reachable矩陣、dp數(shù)組便于驗(yàn)證。理解矛盾情況如果題目數(shù)據(jù)可能無解我們的DP算法也能處理最終答案就是所有dp[i]的最大值至少為1。如果存在環(huán)原圖的拓?fù)渑判驎?huì)失敗可以在開始時(shí)檢測。6. 競賽實(shí)戰(zhàn)策略與總結(jié)回顧這道“遞增序列”它的難度在于將兩個(gè)不同維度的約束下標(biāo)拓?fù)湫蚝蛿?shù)值大小序融合到一個(gè)模型中。競賽中遇到此類問題可以遵循以下步驟問題轉(zhuǎn)化識別出強(qiáng)制約束題目給出的和弱約束問題定義隱含的如遞增。思考能否將弱約束轉(zhuǎn)化為在滿足強(qiáng)約束下的優(yōu)化目標(biāo)。圖論建模當(dāng)涉及“順序”、“前后”約束時(shí)優(yōu)先考慮有向圖。點(diǎn)代表元素邊代表順序關(guān)系。統(tǒng)一條件嘗試將兩種約束統(tǒng)一到同一個(gè)圖上。如果難以統(tǒng)一則考慮在動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移中同時(shí)檢查兩個(gè)條件如我們最終的修正算法。選擇算法在DAG上求最長路徑拓?fù)渑判駾P是標(biāo)準(zhǔn)做法。預(yù)處理傳遞閉包可達(dá)性矩陣是處理復(fù)雜前后關(guān)系判斷的常用技巧。復(fù)雜度分析估算數(shù)據(jù)規(guī)模N, M選擇合適的數(shù)據(jù)結(jié)構(gòu)鄰接表、BitSet。O(N^2)對于1000量級是安全的。代碼實(shí)現(xiàn)注意0-based和1-based轉(zhuǎn)換。使用清晰的變量名。將圖構(gòu)建、傳遞閉包計(jì)算、DP求解模塊化。測試與調(diào)試務(wù)必測試邊界情況N1M0所有a[i]相同約束形成鏈約束形成多個(gè)連通分量以及可能產(chǎn)生矛盾的情況。對于JAVA選手熟練使用ArrayList、Queue、BitSet、StringTokenizer用于快速輸入是基本功。在時(shí)間緊張的情況下可以準(zhǔn)備一些圖算法的模板代碼。這道題的價(jià)值在于它打破了“LIS必須用DP”的思維定式引入了拓?fù)浼s束將線性DP與圖論相結(jié)合。理解其本質(zhì)后可以舉一反三解決一類“帶約束的最優(yōu)序列”問題。例如有些問題約束是“某些元素不能相鄰”則可以轉(zhuǎn)化為圖上沒有邊相連約束是“某些元素必須間隔k個(gè)位置”則可以轉(zhuǎn)化為更復(fù)雜的圖模型。關(guān)鍵在于抽取約束的本質(zhì)并將其轉(zhuǎn)化為圖上的邊或動(dòng)態(tài)規(guī)劃的狀態(tài)限制。