我要急眼了，看了一个破博客写错的浪费我两个小时
Task 1
先讲讲最简单的类型。
通常，都是一类类似 \(f_i=\min_{j=1}^i f_j+w(i,j)\)
决策单调，字面意思，就是每次取的点都是右移的。
先声明一下，四边形不等式是决策单调性的充分不必要条件。
只证明充分条件。
令 \(w\) 满足 \(w(a,c)+w(b,d)\le w(a,d)+w(b,c)\)
我们思考反证法，对于 \(a<b<c<d\) ，不妨设 \(c\) 的决策点是 \(b\) ，\(d\) 的决策点是 \(a\) 。
如果满足决策单调性，换句话说，就是满足：
\[f_b+w(b,c)\le f_a+w(a,c) \]\[f_b+w(b,d)\ge f_a+w(a,d) \]整理，得到：
\[w(b,c)-w(b,d)\le w(a,c)-w(a,d) \]移项
\[w(a,d)+w(b,c)\le w(a,c)+w(b,d) \]与四边形不等式矛盾。
因此，只能反证，有篇博客证充要条件的就是误人子弟。
画个图就能简单易懂，四边形对角线长度和大于等于对边长度和，这是反着的，即对边比对角线和长。你也可以记为包含大于相交。
难搞证明的式子，根据前人的人类智慧，我们只需要证明 \(\forall a<b,w(a,b)+w(a+1,b+1)\le w(a,b+1)+w(a+1,b)\) 即可，可以理解为取 \(a<a+1<c<c+1\) 四个点。为什么是对的呢？因为前人智慧已经证明了。
如果 \(w(a,b)\) 满足四边形不等式，那么就可以使用决策单调性优化。
注意：一定是上面的式子，而不是另一个不等式：\(w(a,b)+w(c,d)<w(a,c)+w(b,d)\)
记住有 \(w(a,d)\) 这一项即可。
例题
P3515 [POI2011] Lightning Conductor
稍微推一下，式子就是 \(f_i\ge \max_{j=1}^{i} a_j+\sqrt{i-j}-a_i\)
这个是取 \(\max\) ，所以我们上述所有推的式子都要取反，也就是说，能使用单调性，需要满足 \(w(a,c)+w(b,d)\ge w(a,d)+w(b,c)\)
明显，这里 \(w(i,j)=\sqrt{i-j}\) ，\(a_i\) 是已经被相减抵消的了。
我们来证明一下 \(w(a,b)+w(a+1,b+1)\ge w(a,b+1)+w(a+1,b)\)
也就是 \(2\sqrt{b-a}\ge \sqrt{b-a+1}+\sqrt{b-a-1}\)
基本不等式即可证明。
至此，我们终于证明了这道题可以使用决策单调性。