四边形不等式

定义

对于形如

$$f_{i,j}=min(f_{i,k}+f_{k+1,j})+s[i][j];$$

的式子，

若s满足四边形不等式，则

$$w_{i,j}+w_{i+1,j+1}<w_{i,j+1}+w_{i+1,j}$$ $$w_{i,j+1}+w_{i+1,j+2}<w_{i,j+2}+w_{i+1,j+1}$$

两边消掉即得

$$w_{i,j}+w_{i+1,j+2}<=w_{i,j+2}+w_{i+1,j}$$

图解四边形不等式：咕掉

石子合并

题意：略（此处要求最小得分）

$$dp_{i,j}=w_{i,j}+min(dp_{i,k}+dp_{k+1,j})$$ $$s_{i,j}=\sum^j_{k=i}a_k$$

此时

$$w_{i,j}+w_{i+1,j+1}<=w_{i+1,j}+w_{i,j+1}$$

而且因为w是区和 ∴此时应该是相等的 证毕（太显然了吧）

总结起来：

若满足1.凸四边形不等式：$w[a][c]+w[b][d]<=w[b][c]+w[a][d]（a<b<c<d）$
2.区间包含关系单调: $w[b][c]<=w[a][d]（a<b<c<d）$

则满足

定理1： 如果w同时满足四边形不等式和决策单调性 ,则f也满足四边形不等式

定理2： 若f满足四边形不等式，则决策s满足 $s[i][j-1]<=s[i][j]<=s[i+1][j]$

定理3： w为凸当且仅当$w[i][j]+w[i+1][j+1]<=w[i+1][j]+w[i][j+1] $