四边形不等式/决策单调性
四边形不等式对于函数 \(w(x,y)\)，如果对于所有的 \(a\leq b \leq c \leq d\) 都满足
\
则称其满足四边形不等式。还有一种等效写法对于 \(l2\)，则必有 \(b-a\) 或 \(d-c\) 有一项大于等于 \(2\)，即求证
\
为 \(b-1\leq b\leq c\leq d\) 的归纳结果证毕。
</blockquote>四边形不等式有一些性质
[*]\(w_1,w_2\) 满足四边形不等式，有常数 \(c_1,c_2\leq 0\)，则 \(c_1w_1+c_2w_2\) 同样满足四边形不等式。
[*]对于任意函数 \(f,g\)，函数 \(w(i,j)=f(i)-g(j)\) 必然满足四边形不等式。
[*]对于一个凸函数 \(h\)，如果 \(w\) 满足区间包含性和四边形不等式，那么 \(w^{'}(i,j)=h(w(i,j))\) 也满足四边形不等式。
区间包含性指对于 \(a\leq b\leq c\leq d\)，有 \(w(a,d)\geq w(b,c)\)。
决策单调性
对于函数 \(f(i)\)，令 \(\text{opt(i)}\) 表示所有能让 \(f(i)\) 取到最值的 \(j\) 的集合，之后通常只考虑 \(\text{opt(i)}\) 的最值即可。令 \(p_i=\max \text{opt(i)}\)（当然最小值也可以）称为最优决策点。
离线情况
对于函数
\
有决策单调性
\[i 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 新版吗？好像是停更了吧。 鼓励转贴优秀软件安全工具和文档！ 收藏一下 不知道什么时候能用到 很好很强大我过来先占个楼 待编辑 感谢分享 谢谢楼主提供！ 分享、互助 让互联网精神温暖你我 懂技术并乐意极积无私分享的人越来越少。珍惜 谢谢楼主提供！ 这个有用。 谢谢分享，辛苦了 谢谢分享，辛苦了 这个有用。 过来提前占个楼 喜欢鼓捣这些软件，现在用得少，谢谢分享！ yyds。多谢分享 谢谢分享，试用一下 鼓励转贴优秀软件安全工具和文档！
页:
[1]
2