四边形不等式（dp优化）应用及证明（石子合并n^2）
石子合并是一道很经典的区间动规。
在n^3的暴力里面，我们的状态转移方程是：
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+w[i][j])
f
[
i
]
[
j
]
=
m
i
n
(
f
[
i
]
[
j
]
,
f
[
i
]
[
k
]
+
f
[
k
+
1
]
[
j
]
+
w
[
i
]
[
j
]
)
现在我们有一种很牛逼的优化，可以把石子合并优化到接近O(n^2)
四边形不等式
我们先来看满足四边形不等式的条件：若
a<b<=c<d
a
<
b
<=
c
<
d
如果有
w[a][c]+w[b][d]<=w[a][d]+w[b][c]
w
[
a
]
[
c
]
+
w
[
b
]
[
d
]
<=
w
[
a
]
[
d
]
+
w
[
b
]
[
c
]
（交叉小于包含）（凸四边形不等式）
那么满足四边形不等式优化。
定理1：如果w满足凸四边形不等式，那么f也满足凸四边形不等式
定理2：如果f满足凸四边形不等式，我们定义
s[i][j]
s
[
i
]
[
j
]
为
f[i][j]
f
[
i
]
[
j
]
在状态转移时取得k为最优，那么
s[i][j]=k
s
[
i
]
[
j
]
=
k
，此时是
s[i][j]
s
[
i
]
[
j
]
满足决策单调性，也就是
s[i][j−1]<=s[i][j]<=s[i+1][j]
s
[
i
]
[
j
−
1
]
<=
s
[
i
]
[
j
]
<=
s
[
i
+
1
]
[
j
]
首先我们先跳过定理的证明（假装我们明白了这些定理的证明咳咳咳），来看看如何通过定理来优化。
既然知道了这个定理，那我们就可以优化掉原本k的那一层循环，转化为优美的O（n^2）啦
代码：
for(int l=3;l<=n;++l)
for(int i=1;i<=n-l+1;++i)
{
int j=i+l-1;
dp[i][j]=INF;
for(int k=s[i][j-1];k<=s[i+1][j];++k)
if((dp[i][k]+dp[k+1][j]+a[j]-a[i-1])<dp[i][j])
s[i][j]=k,dp[i][j]=dp[i][k]+dp[k+1][j]+a[j]-a[i-1];
}ps：O(n)预处理出s[i][i+1]与dp[i][i+1]
简单证明
下面我们来证明几个定理。
假设我们已经证明出了
w[a][c]+w[b][d]<=w[a][d]+w[b][c]（a<b<=c<d）
w
[
a
]
[
c
]
+
w
[
b
]
[
d
]
<=
w
[
a
]
[
d
]
+
w
[
b
]
[
c
]
（
a
<
b
<=
c
<
d
）
现在我们来推导f函数也满足四边形不等式。
假设
s[a][d]=s,s[b][c]=t
s
[
a
]
[
d
]
=
s
,
s
[
b
]
[
c
]
=
t
由于对称性，我们可以假设
s<t
s
<
t
（也就是说反过来也可以）
那么我们可以得到
s+1<t+1<c<d
s
+
1
<
t
+
1
<
c
<
d
那么
f[a][c]+f[b][d]<=f[a][s]+f[s+1][c]+w[a][c]+f[b][t]+f[t+1][d]+w[b][d]
f
[
a
]
[
c
]
+
f
[
b
]
[
d
]
<=
f
[
a
]
[
s
]
+
f
[
s
+
1
]
[
c
]
+
w
[
a
]
[
c
]
+
f
[
b
]
[
t
]
+
f
[
t
+
1
]
[
d
]
+
w
[
b
]
[
d
]
<=f[a][s]+f[s+1][c]+f[b][t]+f[t+1][d]+w[a][d]+w[b][c]
<=
f
[
a
]
[
s
]
+
f
[
s
+
1
]
[
c
]
+
f
[
b
]
[
t
]
+
f
[
t
+
1
]
[
d
]
+
w
[
a
]
[
d
]
+
w
[
b
]
[
c
]
<script type="math/tex" id="MathJax-Element-147"><=f[a][s]+f[s+1][c]+f[b][t]+f[t+1][d]+w[a][d]+w[b][c]</script>
<=f[a][s]+f[t+1][c]+f[b][t]+f[z+1][d]+w[a][d]+w[b][c]
<=
f
[
a
]
[
s
]
+
f
[
t
+
1
]
[
c
]
+
f
[
b
]
[
t
]
+
f
[
z
+
1
]
[
d
]
+
w
[
a
]
[
d
]
+
w
[
b
]
[
c
]
<script type="math/tex" id="MathJax-Element-148"><=f[a][s]+f[t+1][c]+f[b][t]+f[z+1][d]+w[a][d]+w[b][c]</script>（用了数学归纳法）
<=f[a][d]+f[b][c]
<=
f
[
a
]
[
d
]
+
f
[
b
]
[
c
]
<script type="math/tex" id="MathJax-Element-149"><=f[a][d]+f[b][c]</script>
得证。
那么我们再来证明定理2 也就是
s[i][j]
s
[
i
]
[
j
]
满足决策单调性
设
fk[i,j]=f[i,k]+f[k,j]，s[i,j]=d
f
k
[
i
,
j
]
=
f
[
i
,
k
]
+
f
[
k
,
j
]
，
s
[
i
,
j
]
=
d
mk[i+1,j]−md[i+1,j])−(mk[i,j]−md[i,j])
m
k
[
i
+
1
,
j
]
−
m
d
[
i
+
1
,
j
]
)
−
(
m
k
[
i
,
j
]
−
m
d
[
i
,
j
]
)
=(mk[i+1,j]+md[i,j])−(md[i+1,j]+mk[i,j])
=
(
m
k
[
i
+
1
,
j
]
+
m
d
[
i
,
j
]
)
−
(
m
d
[
i
+
1
,
j
]
+
m
k
[
i
,
j
]
)
=(m[i+1,k]+m[k,j]+m[i,d]+m[d,j])−(m[i+1,d]+m[d,j]+m[i,k]+m[k,j])
=
(
m
[
i
+
1
,
k
]
+
m
[
k
,
j
]
+
m
[
i
,
d
]
+
m
[
d
,
j
]
)
−
(
m
[
i
+
1
,
d
]
+
m
[
d
,
j
]
+
m
[
i
,
k
]
+
m
[
k
,
j
]
)
=(m[i+1,k]+m[i,d])−(m[i+1,d]+m[i,k])
=
(
m
[
i
+
1
,
k
]
+
m
[
i
,
d
]
)
−
(
m
[
i
+
1
,
d
]
+
m
[
i
,
k
]
)
∵m满足四边形不等式
∴对于
i<i+1≤k<d
i
<
i
+
1
≤
k
<
d
有
m[i+1,k]+m[i,d]≥m[i+1,d]+m[i,k]
m
[
i
+
1
,
k
]
+
m
[
i
,
d
]
≥
m
[
i
+
1
,
d
]
+
m
[
i
,
k
]
∴
(mk[i+1,j]−md[i+1,j])≥(mk[i,j]−md[i,j])≥0
(
m
k
[
i
+
1
,
j
]
−
m
d
[
i
+
1
,
j
]
)
≥
(
m
k
[
i
,
j
]
−
m
d
[
i
,
j
]
)
≥
0
∴
s[i,j]≤s[i+1,j]
s
[
i
,
j
]
≤
s
[
i
+
1
,
j
]
，同理可证
s[i,j−1]≤s[i,j]
s
[
i
,
j
−
1
]
≤
s
[
i
,
j
]
证毕