反悔貪心分為反悔堆和反悔自動機，其中反悔自動機比較高級。

反悔堆

反悔堆一般維護的是當前決策中的最劣決策，如果有更優決策就會替換最劣決策，一般用堆維護。

例題：建筑搶修

如果可以修直接修，然后把消耗時間放進堆里，如果不能修就找堆里有沒有消耗時間比當前多的，替換一下一定不劣。

反悔自動機

這個比較高級，我個人理解這兩者的區別在于反悔堆需要和以前的操作比較，然后考慮是否反悔，而且不會重復考慮一個決策，一般用于有順序的 \(01\) 決策問題。

而反悔自動機是在貪心過程中融入的反悔過程。

例題：種樹

這個題就十分巧妙啊，當你選了一個點后，他會把這個點的權值賦為旁邊兩個點的權值 \(y_1,y_2\) 的和減去這個點的原權值 \(x\)。

這樣，如果在后面的決策中選了這個新權值，答案為 \(x + y_1 + y_2 - x\)，即為 \(y_1+y_2\)，就成功地進行了一次反悔。

總結

反悔貪心實際上就是給正常的貪心多了一個反悔的機會，而有時普通貪心無法是局部最優到達全局最優，所以這時會有兩個做法，一個是 dp，一個是反悔貪心，dp 的轉移類似于在一個 DAG 上，而對于反悔貪心來說，每個決策點選擇后，向答案貢獻，先后將這個決策點刪除，然后新建一個反悔決策點，或者是，直接用更優的決策替換。