1. 項目概述從一道國賽真題看算法思維的深度最近在整理歷年藍橋杯的真題翻到了第十屆國賽JAVA B組的“遞增序列”這道題。說實話第一次看到題目描述時感覺它像是一道經(jīng)典的動態(tài)規(guī)劃問題但仔細琢磨其輸入輸出格式和約束條件后發(fā)現(xiàn)它的內(nèi)核遠比單純的“最長遞增子序列LIS”要精巧。這道題不僅考察了對基礎(chǔ)算法模型的掌握更考驗選手在特定場景下對問題進行抽象、轉(zhuǎn)化和優(yōu)化的綜合能力。它不像一些直白的搜索或模擬題其難點在于識別出題目給出的“序列”背后隱藏著一個經(jīng)典的圖論模型——拓撲排序或者更準確地說是求解有向無環(huán)圖DAG的最長路徑。對于正在備賽藍橋杯尤其是目標沖擊國賽的JAVA選手來說這類題目具有極高的研究價值。它完美地區(qū)分了“只會套模板”和“真正理解算法本質(zhì)”的選手。通過這道題我們可以深入探討幾個核心問題如何從問題描述中提取關(guān)鍵約束并建立數(shù)學模型當經(jīng)典算法如LIS的O(nlogn)解法無法直接應(yīng)用時如何尋找突破口在JAVA實現(xiàn)中有哪些數(shù)據(jù)結(jié)構(gòu)能高效地支撐我們的算法邏輯以及面對看似復(fù)雜的條件如何設(shè)計清晰、健壯的代碼結(jié)構(gòu)接下來我將結(jié)合我的解題經(jīng)驗徹底拆解這道題分享從問題分析、思路推導(dǎo)到代碼實現(xiàn)與調(diào)試的全過程并提供一些在競賽實戰(zhàn)中非常實用的技巧和避坑指南。2. 問題本質(zhì)與數(shù)學模型構(gòu)建2.1 題目核心需求解析首先我們需要拋開“遞增序列”這個字面名稱的干擾回歸題目本身的具體描述基于常見題型還原。題目通常會給出一個包含N個整數(shù)的序列A以及M組約束條件。每組約束條件形如(x, y)表示在最終要找的“遞增序列”中元素A[x]必須出現(xiàn)在元素A[y]之前即索引x處的值必須在索引y處的值前面。我們的目標是找出滿足所有給定約束條件的、最長的遞增子序列的長度。這里的關(guān)鍵詞是“約束”。普通的LIS問題只關(guān)心數(shù)值的大小關(guān)系a[i] a[j]而本題額外增加了位置的前后關(guān)系約束。這直接導(dǎo)致我們無法直接使用經(jīng)典的LIS動態(tài)規(guī)劃解法因為DP狀態(tài)轉(zhuǎn)移方程dp[i] max(dp[j]) 1 (j i 且 a[j] a[i])只考慮了j在i之前但這里的“之前”僅指原序列中的下標順序并未考慮我們額外添加的(x, y)約束。可能存在著j i但約束要求a[i]必須在a[j]之前的情況這就產(chǎn)生了矛盾。因此我們必須將這兩種關(guān)系統(tǒng)一起來。一個非常自然的想法是構(gòu)建一個有向圖。圖中的每個節(jié)點代表原序列中的一個位置或該位置的值。如果存在約束(x, y)則添加一條從節(jié)點x指向節(jié)點y的有向邊表示x必須排在y之前。同時數(shù)值本身的大小關(guān)系a[i] a[j]也是一種潛在的先后關(guān)系如果我們要將兩者都選入遞增序列那么值小的必須排在值大的前面。但這里需要注意數(shù)值關(guān)系不是強制約束它是一種可選的關(guān)系只有當我們決定同時選取這兩個數(shù)時這個先后關(guān)系才需要被滿足。2.2 從約束到有向無環(huán)圖DAG的轉(zhuǎn)化上述分析引出了核心建模步驟我們最終需要找到一個節(jié)點的排列即子序列使得這個排列同時滿足兩類“先后”關(guān)系強制拓撲序?qū)τ谒薪o定的(x, y)約束在排列中x必須出現(xiàn)在y之前。數(shù)值大小序?qū)τ谂帕兄腥我鈨蓚€不同的元素a[i]和a[j]如果a[i] a[j]那么在排列中i必須出現(xiàn)在j之前這是由“遞增”序列的定義決定的。為了讓問題可解我們需要將這兩種序合并。一個巧妙且正確的思路是利用強制拓撲序來“傳遞”數(shù)值關(guān)系。具體來說我們首先根據(jù)M個約束條件構(gòu)建初始的有向圖。然后對于任意兩個節(jié)點i和ji ! j如果a[i] a[j]并且在原圖中存在從i到j(luò)的路徑即j在拓撲序上依賴于i那么我們就添加一條從i到j(luò)的有向邊。為什么因為如果j依賴于ii必須在j前同時a[i] a[j]那么當我們同時選擇i和j時i在j之前自然就滿足了數(shù)值遞增的要求。這條邊強化了它們之間的先后關(guān)系。然而這里有一個巨大的陷阱如果a[i] a[j]但原圖中存在從j到i的路徑即i依賴于j這就產(chǎn)生了矛盾。因為這意味著題目給出的約束要求i在j后面但數(shù)值關(guān)系要求i值小在j值大前面才能構(gòu)成遞增兩者無法同時滿足。在這種情況下節(jié)點i和j絕對不可能同時出現(xiàn)在任何一個合法的遞增序列中。在算法中我們需要檢測這種矛盾。一種方法是在嘗試添加數(shù)值關(guān)系邊之前先檢查兩個節(jié)點是否已經(jīng)在原約束下互斥即存在雙向路徑或形成了環(huán)。更普適的方法是在構(gòu)建完最終圖后檢查圖中是否存在環(huán)。如果存在環(huán)則說明約束存在矛盾可能無解但根據(jù)藍橋杯賽題特點通常數(shù)據(jù)保證有解。最終我們會得到一個擴充后的有向圖G。這個圖G包含了所有必須遵守的先后順序。我們的目標轉(zhuǎn)化為在圖G中尋找一條最長的路徑且路徑上節(jié)點的權(quán)值即原序列的a[i]是嚴格遞增的。由于數(shù)值遞增的要求已經(jīng)通過我們添加邊的策略僅當a[i] a[j]且i能到達j時才加邊融入了圖中因此在這個新圖G中找一條最長路徑路徑上的節(jié)點自然滿足數(shù)值遞增。問題進一步簡化為在DAG上求最長路徑。注意這里有一個極其關(guān)鍵的思維跳躍。為什么可以簡化成“DAG上的最長路徑”因為我們添加邊的策略保證了如果圖中有一條從u到v的邊那么一定有a[u] a[v]且 u 必須排在 v 之前。因此圖中的任意一條路徑其節(jié)點對應(yīng)的數(shù)值必然是遞增的并且滿足所有約束。所以找最長的滿足條件的遞增子序列等價于在這個DAG上找最長的路徑。這是一個非常經(jīng)典的模型轉(zhuǎn)化。2.3 算法選型與復(fù)雜度初估模型建立后算法選擇就清晰了圖構(gòu)建使用鄰接表存儲圖。首先添加M條約束邊。然后需要高效判斷任意兩點間是否存在路徑以決定是否添加數(shù)值關(guān)系邊。直接使用Floyd-Warshall求傳遞閉包是O(N^3)對于N可能達到10^3的數(shù)量級是不可接受的。通常競賽數(shù)據(jù)中M約束數(shù)不會極大我們可以采用拓撲排序BFS/DFS的方式為每個節(jié)點預(yù)處理出其可到達的節(jié)點集合。但這仍然是O(N*(NM))在N1000時可能處于臨界狀態(tài)需要謹慎實現(xiàn)。最長路徑求解在DAG上求最長路徑是標準拓撲排序動態(tài)規(guī)劃。設(shè)dp[i]表示以節(jié)點i為終點的最長路徑長度。狀態(tài)轉(zhuǎn)移方程為dp[i] max(dp[j]) 1其中j是所有有邊指向i的節(jié)點。初始化dp[i] 1每個節(jié)點自身構(gòu)成長度為1的路徑。我們按照拓撲序依次更新dp值即可。整個算法的瓶頸在于圖的構(gòu)建階段尤其是處理數(shù)值關(guān)系邊。我們需要一個高效的“可達性判斷”方法。3. 核心實現(xiàn)細節(jié)與優(yōu)化策略3.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計與圖構(gòu)建在JAVA中我們?nèi)绾胃咝У乇硎緢D和進行可達性判斷呢鄰接表存儲使用ArrayListArrayListInteger graph是最直觀的方式。但為了同時高效地進行拓撲排序和DP我們還需要記錄每個節(jié)點的入度int[] inDegree。可達性判斷優(yōu)化直接對每對(i, j)進行DFS/BFS檢查是否可達復(fù)雜度太高。一個可行的優(yōu)化是利用位集BitSet來存儲每個節(jié)點的后繼集合。JAVA中的java.util.BitSet非常節(jié)省空間且位運算速度快。我們創(chuàng)建一個BitSet[] reachable數(shù)組其中reachable[i]是一個BitSet表示從節(jié)點i出發(fā)可以到達哪些節(jié)點。首先根據(jù)M條約束邊構(gòu)建初始圖并通過記憶化DFS或拓撲排序后遞推的方式填充reachable數(shù)組。這是一個傳遞閉包的計算過程。對于DAG可以在拓撲逆序上遞推reachable[i].or(reachable[v])對于每個從i指向v的邊并且reachable[i].set(i)。然后遍歷所有節(jié)點對(i, j)如果a[i] a[j]且reachable[i].get(j)為真則在圖中添加一條從i到j(luò)的邊注意去重并更新inDegree[j]。同時如果a[i] a[j]但reachable[j].get(i)為真則說明i和j互相依賴但數(shù)值要求順序相反理論上它們不能共存。不過由于我們只添加i-j的邊如果j-i的路徑存在那么i和j就在同一個環(huán)里了嗎不一定但添加i-j邊后結(jié)合原有的j-i路徑就會形成環(huán)。因此更安全的做法是在添加邊后檢查圖中是否產(chǎn)生環(huán)。或者在添加邊時直接判斷如果reachable[j].get(i)為真則跳過添加i-j這條邊因為已有的約束已經(jīng)要求j在i前這與數(shù)值關(guān)系沖突同時選擇它們會違反約束。構(gòu)建圖的具體步驟讀取N序列a[]M以及M條約束。初始化graphinDegreereachable(每個BitSet大小為N)。添加M條約束邊更新graph和inDegree。通過拓撲排序或DFS計算初始的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不能同時被選入序列。對于本題求最長路徑我們的處理方式是不添加任何邊。因為添加任何邊都會導(dǎo)致環(huán)或邏輯矛盾。在最終的DAG中i和j之間將沒有邊相連最長路徑算法可能會選擇其中一個但不會同時選擇兩者這符合邏輯。重新初始化inDegree數(shù)組基于新圖計算。3.2 DAG最長路徑的動態(tài)規(guī)劃求解在得到最終的DAG后求解最長路徑就是標準流程拓撲排序使用隊列將所有入度為0的節(jié)點入隊。依次出隊節(jié)點u將其加入拓撲序列表topoOrder并遍歷其所有鄰接點v將inDegree[v]--若減為0則入隊。動態(tài)規(guī)劃初始化dp[]全為1。按照topoOrder的順序遍歷節(jié)點u對于u的每個后繼v執(zhí)行dp[v] Math.max(dp[v], dp[u] 1)。獲取答案遍歷所有節(jié)點的dp[i]最大值即為所求最長遞增且滿足約束子序列的長度。這個部分的代碼相對模板化但需要注意細節(jié)確保拓撲排序能正常完成即出隊節(jié)點數(shù)等于總節(jié)點數(shù)否則說明圖中有環(huán)這與題目假設(shè)可能不符但代碼中最好做異常處理。3.3 邊界條件與初始化心得在實際編碼中一些邊界條件容易忽略節(jié)點編號題目通常使用1-based索引而我們的代碼習慣使用0-based。需要在輸入輸出時進行轉(zhuǎn)換內(nèi)部存儲統(tǒng)一用0-based避免混亂。去重邊在添加數(shù)值關(guān)系邊時同一條邊可能因為不同的數(shù)值對關(guān)系被多次嘗試添加。使用HashSet存儲每個節(jié)點的鄰接表或者在添加前檢查鄰接關(guān)系可以避免重復(fù)邊影響入度計算。BitSet內(nèi)存BitSet大小設(shè)為N。當N很大時比如10^5BitSet數(shù)組的內(nèi)存占用約為N^2 / 8字節(jié)對于N1000大約是125KB可以接受但如果N達到10000就會約12.5MB可能超出內(nèi)存限制。這時就需要更精細的優(yōu)化例如只對必要的節(jié)點對進行檢查或者采用分塊等策略。藍橋杯國賽B組的數(shù)據(jù)規(guī)模通常會控制在不必須使用極端優(yōu)化的情況下。序列值相等題目要求是“遞增”通常是嚴格遞增a[i] a[j]。如果出現(xiàn)相等值根據(jù)定義它們不能同時出現(xiàn)在遞增序列中。在我們的算法中對于a[i] a[j]的情況不會添加邊這是正確的。4. 代碼實現(xiàn)與逐行解析下面給出一個完整的JAVA實現(xiàn)并穿插關(guān)鍵注釋。假設(shè)輸入格式為第一行整數(shù)N第二行N個整數(shù)表示序列a第三行整數(shù)M接下來M行每行兩個整數(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. 計算初始傳遞閉包 (拓撲排序遞推) 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) 為真說明有沖突不添加邊 // 我們的算法中這種情況不會執(zhí)行添加操作符合邏輯 } } } // 5. 在新圖上進行拓撲排序求最長路徑 graph newGraph; inDegree newInDegree; int ans longestPathInDAG(); System.out.println(ans); } // 計算傳遞閉包通過拓撲排序的逆序遞推 static void calcReachable() { // 拓撲排序 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); // 自身可達 for (int v : graph.get(u)) { reachable[u].or(reachable[v]); // u可達v并且可達v能到的所有點 } } } // 在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)鍵。我們首先進行一次拓撲排序得到拓撲序topo。然后逆序遍歷這個拓撲序。為什么逆序因為對于節(jié)點u它的可達集合等于它所有直接后繼v的可達集合的并集再加上它自己。逆序保證了當處理u時它的所有后繼v都已經(jīng)被處理過了reachable[v]已經(jīng)是完整的可以直接進行or操作。添加數(shù)值關(guān)系邊的雙重循環(huán)這里復(fù)雜度是O(N^2)在N1000時是10^6可以接受。內(nèi)層判斷reachable[i].get(j)是O(1)的位操作極快。重建圖我們在添加新邊時創(chuàng)建了newGraph和newInDegree而不是在原圖上修改。這是因為添加邊是增量過程直接在原圖上修改入度會干擾后續(xù)的邊添加判斷。全部確定后再替換是更清晰的做法。longestPathInDAG()函數(shù)標準的拓撲排序DP。dp[i]初始為1表示路徑至少包含自己。在松弛操作dp[v] Math.max(dp[v], dp[u] 1)中我們總是用更長的路徑來更新。5. 常見問題與調(diào)試技巧實錄即使思路清晰在實現(xiàn)這道題時依然會遇到不少坑。以下是我在調(diào)試和教學過程中總結(jié)的常見問題1. 超時問題癥狀程序在較大數(shù)據(jù)如N1000, M2000下運行超時。排查首先檢查是否是O(N^3)的Floyd-Warshall求傳遞閉包。我們的calcReachable方法是O(N*(NM))在稀疏圖下接近O(N^2)。如果仍然超時可能是BitSet的or操作在N很大時開銷大。可以嘗試優(yōu)化只在reachable[i]和reachable[v]都是稀疏集時才有優(yōu)勢如果很稠密用boolean[][]數(shù)組可能更快但空間是O(N^2)。需要權(quán)衡。對于藍橋杯環(huán)境BitSet通常是夠用的。優(yōu)化技巧在添加數(shù)值關(guān)系邊的循環(huán)中可以做一些剪枝。例如如果a[i]已經(jīng)很大那么滿足a[i] a[j]的j可能不多。可以事先將節(jié)點按值排序但會破壞索引關(guān)系實現(xiàn)復(fù)雜。一個簡單的優(yōu)化是內(nèi)層循環(huán)j可以從i1開始因為(i, j)和(j, i)會判斷兩次但我們的條件a[i] a[j]是不對稱的所以不能簡單減半。不過如果同時檢查reachable[i].get(j)和reachable[j].get(i)可以只遍歷ij的對。2. 答案錯誤癥狀樣例通過但提交后部分測試點錯誤。排查步驟檢查圖是否成環(huán)在longestPathInDAG中最后可以檢查一下出隊節(jié)點數(shù)量是否等于N。如果不等于說明新構(gòu)建的圖中有環(huán)這意味著我們的添加邊邏輯有誤可能產(chǎn)生了矛盾環(huán)。添加一段檢測代碼如果idx ! N輸出-1或進行調(diào)試。驗證傳遞閉包編寫一個小型測試打印出reachable數(shù)組看是否與手動推導(dǎo)的一致。特別注意reachable[i].get(i)必須為真。檢查數(shù)值關(guān)系邊的添加條件最易錯的點。必須確保只在a[i] a[j]且i能到達j的情況下添加i-j邊。如果a[i] a[j]但j能到達i則不能添加邊否則成環(huán)。如果兩者互不可達呢那么它們之間沒有約束可以任意排序但數(shù)值上a[i] a[j]如果我們想同時選它們必須保證i在j前。然而原圖沒有路徑我們能否添加一條邊來建立這個順序不能因為添加這條邊就人為增加了一個約束可能會影響其他節(jié)點。例如可能存在k有i-k和k-j的路徑但i不能直接到j(luò)。如果我們添加i-j就創(chuàng)建了一條捷徑可能使得一些原本不合法的路徑變得合法這里需要仔細思考。實際上正確的理解是如果i和j在原約束下無關(guān)即互不可達那么它們可以以任意順序出現(xiàn)在序列中。但是如果我們想同時選取它們構(gòu)成遞增就必須決定一個順序。這個順序的選擇會影響最終最長路徑。我們的算法選擇不添加邊意味著在最終的DAG中i和j之間沒有邊。那么最長路徑算法可能會選擇經(jīng)過i或經(jīng)過j的路徑但不會有一條路徑同時包含i和j因為圖里沒有連接它們的邊。這可能會導(dǎo)致丟失最優(yōu)解。這是一個深坑修正方案對于互不可達的i, j且a[i] a[j]我們應(yīng)該添加邊嗎考慮一個簡單例子序列[1, 2]沒有約束。最長遞增子序列是[1, 2]。如果我們在構(gòu)建圖時因為1和2互不可達就不加邊那么最終圖是空的每個節(jié)點獨立最長路徑是1答案錯誤。所以對于原圖中互不可達的節(jié)點數(shù)值關(guān)系應(yīng)該被考慮為一種可能的順序。但直接添加i-j邊是危險的因為它引入了新的拓撲關(guān)系可能會影響第三方節(jié)點。更安全的做法是不修改原圖而是在動態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移時同時考慮數(shù)值關(guān)系和拓撲關(guān)系。但這會使DP變得復(fù)雜。3. 算法修正更準確的模型與實現(xiàn)上述分析揭示了之前算法的缺陷。正確的做法應(yīng)該是最終的圖只包含題目給定的M條強制約束邊。數(shù)值關(guān)系不預(yù)先作為邊加入圖中而是在動態(tài)規(guī)劃過程中作為轉(zhuǎn)移條件。重新定義狀態(tài)與轉(zhuǎn)移dp[i]表示以第i個元素結(jié)尾的、滿足所有約束的最長遞增子序列長度。轉(zhuǎn)移方程dp[i] max(dp[j] 1)其中j需要滿足兩個條件拓撲約束在原約束圖G中存在從j到i的路徑即j必須能到達i或者j和i在原圖中是無關(guān)的互不可達。簡單說就是不能存在從i到j(luò)的路徑否則i必須在j前矛盾。數(shù)值約束a[j] a[i]。這個轉(zhuǎn)移方程的正確性在于它保證了對于序列中任意相鄰的兩項它們既滿足數(shù)值遞增也滿足拓撲約束要么有路徑保證順序要么原本無約束可以自由排列。實現(xiàn)難點條件1的判斷需要在DP過程中頻繁進行。我們可以預(yù)處理一個boolean[][] reachable矩陣或BitSet[]reachable[i][j]為真表示i能到達j。那么條件1就是!reachable[i][j]即i不能到達j。因為如果i能到達j那么i必須排在j前面而我們是以j結(jié)尾尋找前面的i這就不合法了。修正后的核心DP代碼static int solve() { // 預(yù)處理原約束圖的傳遞閉包 reachable calcReachable(); // 計算原圖的reachable graph是原約束圖 int[] dp new int[N]; Arrays.fill(dp, 1); int ans 1; // 按照某種順序進行DP需要保證在計算dp[i]時所有可能的j都已經(jīng)計算過。 // 由于約束可能復(fù)雜簡單的從左到右遍歷不行。我們需要一個拓撲序但這里的拓撲序是針對原約束圖的。 // 一個穩(wěn)妥的順序是先對原約束圖進行拓撲排序按這個順序DP。 int[] topoOrder getTopoOrderOfOriginalGraph(); for (int i : topoOrder) { for (int j 0; j N; j) { if (i j) continue; // 條件1: j 不能到達 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的前一個元素因為順序反了。所以我們需要的是!reachable[j][i]。同時我們還需要考慮j和i互不可達的情況這也是滿足條件的。這個算法的時間復(fù)雜度是O(N^2)對于N1000是可行的。它避免了構(gòu)建復(fù)雜的新圖邏輯更清晰直接。4. 內(nèi)存溢出使用boolean[N][N]存儲可達矩陣當N5000時需要約25MB5000*5000/8/1024/1024 ≈ 23.8MB可能接近內(nèi)存限制。使用BitSet[N]可以節(jié)省約8倍空間。在藍橋杯環(huán)境中通常N在1000左右boolean[1000][1000]約1MB是安全的。調(diào)試心得從小樣例開始構(gòu)造N3,4的小數(shù)據(jù)包含各種情況有約束、無約束、數(shù)值相等、有環(huán)沖突手動計算答案與程序輸出對比。打印中間狀態(tài)在關(guān)鍵步驟后如構(gòu)建完圖、計算完DP打印出圖的結(jié)構(gòu)、reachable矩陣、dp數(shù)組便于驗證。理解矛盾情況如果題目數(shù)據(jù)可能無解我們的DP算法也能處理最終答案就是所有dp[i]的最大值至少為1。如果存在環(huán)原圖的拓撲排序會失敗可以在開始時檢測。6. 競賽實戰(zhàn)策略與總結(jié)回顧這道“遞增序列”它的難度在于將兩個不同維度的約束下標拓撲序和數(shù)值大小序融合到一個模型中。競賽中遇到此類問題可以遵循以下步驟問題轉(zhuǎn)化識別出強制約束題目給出的和弱約束問題定義隱含的如遞增。思考能否將弱約束轉(zhuǎn)化為在滿足強約束下的優(yōu)化目標。圖論建模當涉及“順序”、“前后”約束時優(yōu)先考慮有向圖。點代表元素邊代表順序關(guān)系。統(tǒng)一條件嘗試將兩種約束統(tǒng)一到同一個圖上。如果難以統(tǒng)一則考慮在動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移中同時檢查兩個條件如我們最終的修正算法。選擇算法在DAG上求最長路徑拓撲排序DP是標準做法。預(yù)處理傳遞閉包可達性矩陣是處理復(fù)雜前后關(guān)系判斷的常用技巧。復(fù)雜度分析估算數(shù)據(jù)規(guī)模N, M選擇合適的數(shù)據(jù)結(jié)構(gòu)鄰接表、BitSet。O(N^2)對于1000量級是安全的。代碼實現(xiàn)注意0-based和1-based轉(zhuǎn)換。使用清晰的變量名。將圖構(gòu)建、傳遞閉包計算、DP求解模塊化。測試與調(diào)試務(wù)必測試邊界情況N1M0所有a[i]相同約束形成鏈約束形成多個連通分量以及可能產(chǎn)生矛盾的情況。對于JAVA選手熟練使用ArrayList、Queue、BitSet、StringTokenizer用于快速輸入是基本功。在時間緊張的情況下可以準備一些圖算法的模板代碼。這道題的價值在于它打破了“LIS必須用DP”的思維定式引入了拓撲約束將線性DP與圖論相結(jié)合。理解其本質(zhì)后可以舉一反三解決一類“帶約束的最優(yōu)序列”問題。例如有些問題約束是“某些元素不能相鄰”則可以轉(zhuǎn)化為圖上沒有邊相連約束是“某些元素必須間隔k個位置”則可以轉(zhuǎn)化為更復(fù)雜的圖模型。關(guān)鍵在于抽取約束的本質(zhì)并將其轉(zhuǎn)化為圖上的邊或動態(tài)規(guī)劃的狀態(tài)限制。