Optimization

反悔贪心是对贪心策略的一种优化，有些时候贪心策略是错的，但如果可以撤销之前的操作，那么就会变为正确的。

另外，有一种观点认为反悔贪心的本质是贪心模拟费用流，我认为是有一定道理的，这种观点也有利于解释反悔贪心的正确性。

反悔贪心板子题。

反悔贪心板子题 \(\times 2\)。

假设有 \(p_{1}\leqslant p_{2}\leqslant p_{3}\leqslant p_{4}.\)

假设一个问题满足四边形不等式，那么它的决策点有单调性。

Proof:

根据最优决策的定义写出这个位置的转移式 :

两不等式相加，得到 :