矩形子數組最大和 - 從暴力 O(m³n³) 到優化 O(m²n) 完整演進
問題描述 給定 m × n 矩陣,求和最大的矩形子陣列。元素可正可負。 暴力解法:六層循環 O(m³n³) 枚舉左上角 (i,j) 和右下角 (ii,jj),
HDU 1520 Anniversary Party - 樹形 DP 最大化派對愉悅度
問題描述 大學員工結構形成一棵樹(根為校長)。每個員工有「愉悅度」評分(可正可負)。選擇受邀名單,使得沒有員工與其直屬上司同時出席,且總愉悅度最大。N ≤ 60
UVA 1452 Jump - 約瑟夫環變形求最後三個被刪除的數
問題描述 1~n 按逆時針排成環,從 1 開始每隔 k 個數刪除一個,直到全部刪除。求最後被刪除的 3 個數字(按刪除順序:倒數第 3、第 2、第 1)。 約
HDU 1864 - 背包問題求找零錢的最大價值
問題描述 給定總金額 Q(單位:分)和 N 組購買項目。每組包含 m 個物品,每物品有類別 A/B/C 和價格。約束條件: 同類別物品總價 ≤ 600 元
UVA 1291 Dance Dance Revolution - 狀態壓縮 DP 解舞步最小體力消耗
問題描述 模擬跳舞機遊戲:腳初始位於 0(中心),面板編號 1-4 分別對應上下左右。給定一系列舞步方向,每步必須移動一隻腳到目標格子。移動消耗體力: 0
UVA 11404 Palindromic Subsequence - LCS 求最長回文子序列且字典序最小
問題描述 給定一個字符串,求其最長回文子序列。若存在多個相同長度的回文子序列,輸出字典序最小的一個。字符串長度 ≤ 1000。 核心觀察:LCS 與回文的關係
UVA 10859 Placing Lampposts - 樹形 DP 經典解法詳解
問題描述 給定一個擁有 n 個節點、m 條邊的無向無環圖(即森林),我們需要在盡可能少的節點上放置路燈,使得所有邊都被照亮。每盞路燈會照亮所有以其為端點的邊。在
BMP 圖像旋轉 180 度:C++ 實現與內存對齊處理
問題描述 讀取 24 位 BMP 文件,將圖像旋轉 180 度(等價於上下翻轉 + 左右翻轉),寫入新文件。需正確處理行內存對齊(4 字節對齊)。 BMP 文
HDU 2594:KMP 求模式最長前綴匹配文本後綴
問題描述 給定 s1(模式)和 s2(文本),長度 ≤ 50000。求 s1 的最長前綴,使其為 s2 的後綴。輸出該前綴及長度;無則輸出 0。 解法:KMP
C++ 日誌文件封裝:時間、文件名、行號自動記錄
需求 實現一個輕量級日誌宏,自動捕獲調用處的文件名(__FILE__)、行號(__LINE__)、當前時間,格式化輸出到文件與控制台。 實現代碼 #incl
POJ 3984:迷宮最短路徑 BFS + 路徑記錄遞歸輸出
問題描述 5×5 迷宮,0 可通行,1 障礙。從 (0,0) 走到 (4,4),輸出最短路徑坐標序列(每行一個坐標)。 解法:BFS + 前驅記錄 BFS 保
HDU 2594 Simpsons' Hidden Talents:KMP 求最長前綴後綴匹配
問題描述 給定字符串 s1(模式)和 s2(文本)。求 s1 的最長前綴,使其為 s2 的後綴。輸出該前綴串及其長度;無則輸出 0。長度 ≤ 50000。 解
POJ 1273 / HDU 1532:最大流模型 - 排水溝 Edmonds-Karp 實現
問題描述 N ≤ 200 條溝,M ≤ 200 個交匯點。1 號點為池塘(源),M 號為河流(匯)。每條溝有容量 C_i,方向固定。求最大流量。 模型:標準最
HDU 4662 MU Puzzle:不變量分析與 BFS 預計算的多校最水題
問題重述 初始串 MI。規則: 1. Mx → Mxx 2. III → U 3. UU → ε 問目標串是否可達。 核心不變量 首字符恒為 M,且只能
HDU 2203:親和字符串判斷 - KMP 搜索循環匹配
問題描述 給定字符串 T 和 P。若 P 是 T 的某個循環移位的子串,輸出 yes,否則 no。即判斷 P 是否為 T+T 的子串(且 |T| ≥ |P|)。