「壓」之貪心

01-28

其實把貪心歸為「壓」是有點牽強的。但我如果把貪心理解成特殊的動態規劃，而動態規劃涉及到狀態壓縮，那麼就合理了。

貪心演算法範圍極廣，腦洞奇大無比，很多題目往往無跡可尋，憑感覺猜結論寫完AC後不證明是常有的事。

諸如最小生成樹、最小費用最大流這些經典的圖論演算法就用到了貪心。

貪心演算法的應用往往由於問題滿足一定性質，使用一些固定的策略可以達到最優解。其中比較著名的有擬證理論（然而我並不會）。

內容不能泛泛而談，但貪心演算法實在太飄渺。我的想法是舉幾道我認為的好題來闡述我所接觸到的一些貪心思想。

例題1-調整思想：給二元組集合|{(Ai,Bi)}|=N，取出一個最大的子集任意排列，使得滿足 $B(i) geq sum_{j=1}^{i-1} A(j) (1 leq i leq n)$

通過局部調整序列，得出最優化的排序條件。

再加一道難的 1738 -- An old Stone Game

例題2-反證思想：求樹的直徑

簡單的找兩次最優的貪心想法為什麼正確？不妨反證來得出矛盾。

例題3-去無效態：k個機器人同時從根出發遍歷完樹的所有節點，問最少總路徑長度。

一棵子樹最後會返回幾個機器人？大於一個是沒有意義的。

例題4-消元思想：給定一個無向圖,求1到n的一條路徑,使得路徑的異或和最大。

路徑由簡單環和一條簡單路徑複合而成。環和環之間可以複合，可以用高斯消元解決。

例題5-數形結合：最小乘乘積生成樹：給定一張有A,B兩種權的圖找一顆生成樹使得 $sum_{ein T} A(e) * sum_{ein T} B(e)$ 最大。

考慮將所有生成樹放在以A的和為x軸，B的和為y軸的二維坐標繫上，通過尋找凸包上的點來更新答案。