设
f
k
,
i
f_{k,i}
fk,i表示前
i
i
i个村庄放了
k
k
k个邮局的最小代价。
则
f
k
,
i
=
min
j
=
0
i
{
f
k
−
1
,
j
+
w
j
+
1
,
i
}
f_{k,i}=\overset{i}{\underset{j=0}\min}\{f_{k-1,j}+w_{j+1,i}\}
fk,i=j=0mini{fk−1,j+wj+1,i} 表示分配给村庄
[
j
+
1
,
i
]
[j+1,i]
[j+1,i]一个邮局。
设
f
0
,
0
=
0
f_{0,0}=0
f0,0=0，其他状态为正无穷。就是
O
(
n
3
)
O(n^3)
O(n3)
贡献函数
w
i
,
j
w_{i,j}
wi,j表示给村庄
[
i
,
j
]
[i,j]
[i,j]分配一个邮局的最小贡献。 显然邮局放在区间下标中位数对应的村庄最优。如果有偶数个村庄放在两个中位数处都可以。 因为如果向着远离中位数的地方移动，那么减少的贡献少，而增加的贡献多。
则
w
i
,
j
=
w
i
,
j
−
1
+
a
j
−
a
⌊
i
+
j
2
⌋
w_{i,j}=w_{i,j-1}+a_j-a_{\left\lfloor \frac {i+j}2\right\rfloor}
wi,j=wi,j−1+aj−a⌊2i+j⌋ 因为当区间长度由奇数向偶数转移时中位数不变，式子肯定成立。 而区间长度为偶数时可以认为邮局位于右边那个中位数处，中位数也可以认为不变。
打表打出决策单调性，于是可以
O
(
n
2
)
O(n^2)
O(n2)：
f
k
,
i
=
min
j
=
p
k
−
1
,
i
p
k
,
i
+
1
{
f
k
−
1
,
j
+
w
j
+
1
,
i
}
f_{k,i}=\overset{p_{k,i+1}}{\underset{j=p_{k-1,i}}\min}\{f_{k-1,j}+w_{j+1,i}\}
fk,i=j=pk−1,iminpk,i+1{fk−1,j+wj+1,i}
证明贡献函数满足四边形不等式： 带入递推式
w
i
,
j
=
w
i
,
j
−
1
+
a
j
−
a
⌊
i
+
j
2
⌋
w_{i,j}=w_{i,j-1}+a_j-a_{\left\lfloor \frac {i+j}2\right\rfloor}
wi,j=wi,j−1+aj−a⌊2i+j⌋就会发现贡献函数显然满足四边形不等式：
w
i
,
j
+
w
i
+
1
,
j
+
1
≤
w
i
,
j
+
1
+
w
i
+
1
,
j
w_{i,j}+\textcolor{blue}{w_{i+1,j+1}}\leq \textcolor{red}{w_{i,j+1}}+w_{i+1,j}
wi,j+wi+1,j+1≤wi,j+1+wi+1,j
w
i
,
j
+
w
i
+
1
,
j
+
w
i
+
1
,
j
+
a
j
+
1
−
a
⌊
i
+
j
−
2
2
⌋
≤
w
i
,
j
+
a
j
+
1
−
a
⌊
i
+
j
−
1
2
⌋
+
w
i
+
1
,
j
w_{i,j}+\textcolor{blue}{w_{i+1,j}+w_{i+1,j}+a_{j+1}-a_{\left\lfloor{\frac{i+j-2}{2}}\right\rfloor}}\leq \textcolor{red}{w_{i,j}+a_{j+1}-a_{\left\lfloor{\frac{i+j-1}{2}}\right\rfloor}}+w_{i+1,j}
wi,j+wi+1,j+wi+1,j+aj+1−a⌊2i+j−2⌋≤wi,j+aj+1−a⌊2i+j−1⌋+wi+1,j
证明状态函数满足四边形不等式： 不需要归纳，直接设
p
i
,
j
+
1
=
x
,
p
i
+
1
,
j
=
y
p_{i,j+1}=x,p_{i+1,j}=y
pi,j+1=x,pi+1,j=y，我们讨论
x
<
y
x<y
x<y的情况： 两个含有
f
i
,
j
,
f
i
+
1
,
j
+
1
\color{blue}f_{i,j},f_{i+1,j+1}
fi,j,fi+1,j+1的不等式：
{
f
i
,
j
≤
f
i
−
1
,
x
+
w
x
+
1
,
j
f
i
+
1
,
j
+
1
≤
f
i
,
y
+
w
y
+
1
,
j
+
1
\left\{\begin{matrix} {\color{blue}{f_{i,j}}}\leq f_{i-1,x}+w_{x+1,j}\;\;\;\;\;\;\\ \textcolor{blue}{f_{i+1,j+1}}\leq f_{i,y}+w_{y+1,j+1} \end{matrix}\right.
{fi,j≤fi−1,x+wx+1,jfi+1,j+1≤fi,y+wy+1,j+1 加起来：
f
i
,
j
+
f
i
+
1
,
j
+
1
≤
f
i
−
1
,
x
+
w
x
+
1
,
j
+
f
i
,
y
+
w
y
+
1
,
j
+
1
\textcolor{blue}{f_{i,j}+f_{i+1,j+1}}\leq f_{i-1,x}+w_{x+1,j}+f_{i,y}+w_{y+1,j+1}
fi,j+fi+1,j+1≤fi−1,x+wx+1,j+fi,y+wy+1,j+1 再加上两个含有
f
i
,
j
+
1
,
f
i
+
1
,
j
\color{red}f_{i,j+1},f_{i+1,j}
fi,j+1,fi+1,j的等式
{
f
i
,
j
+
1
=
f
i
−
1
,
x
+
w
x
+
1
,
j
+
1
f
i
+
1
,
j
=
f
i
,
y
+
w
y
+
1
,
j
\left\{\begin{matrix} {\color{red}f_{i,j+1}}=f_{i-1,x}+w_{x+1,j+1}\\ {\color{red}f_{i+1,j}}=f_{i,y}+w_{y+1,j}\;\;\;\;\;\;\; \end{matrix}\right.
{fi,j+1=fi−1,x+wx+1,j+1fi+1,j=fi,y+wy+1,j 加到不等式的右边去：
f
i
,
j
+
f
i
+
1
,
j
+
1
+
f
i
−
1
,
x
+
w
x
+
1
,
j
+
1
+
f
i
,
y
+
w
y
+
1
,
j
≤
f
i
,
j
+
1
+
f
i
+
1
,
j
+
f
i
−
1
,
x
+
w
x
+
1
,
j
+
f
i
,
y
+
w
y
+
1
,
j
+
1
\textcolor{blue}{f_{i,j}+f_{i+1,j+1}}+f_{i-1,x}+w_{x+1,j+1}+f_{i,y}+w_{y+1,j}\leq {\color{red}f_{i,j+1}}+{\color{red}f_{i+1,j}}+f_{i-1,x}+w_{x+1,j}+f_{i,y}+w_{y+1,j+1}
fi,j+fi+1,j+1+fi−1,x+wx+1,j+1+fi,y+wy+1,j≤fi,j+1+fi+1,j+fi−1,x+wx+1,j+fi,y+wy+1,j+1
f
i
,
j
+
f
i
+
1
,
j
+
1
+
w
x
+
1
,
j
+
1
+
w
y
+
1
,
j
≤
f
i
,
j
+
1
+
f
i
+
1
,
j
+
w
x
+
1
,
j
+
w
y
+
1
,
j
+
1
\textcolor{blue}{f_{i,j}+f_{i+1,j+1}}+w_{x+1,j+1}+w_{y+1,j}\leq {\color{red}f_{i,j+1}}+{\color{red}f_{i+1,j}}+w_{x+1,j}+w_{y+1,j+1}
fi,j+fi+1,j+1+wx+1,j+1+wy+1,j≤fi,j+1+fi+1,j+wx+1,j+wy+1,j+1 对不等式左边用贡献函数的四边形不等式：
f
i
,
j
+
f
i
+
1
,
j
+
1
+
w
x
+
1
,
j
+
w
y
+
1
,
j
+
1
≤
f
i
,
j
+
1
+
f
i
+
1
,
j
+
w
x
+
1
,
j
+
w
y
+
1
,
j
+
1
{f_{i,j}+f_{i+1,j+1}}+w_{x+1,j}+w_{y+1,j+1}\leq {f_{i,j+1}}+{f_{i+1,j}}+w_{x+1,j}+w_{y+1,j+1}
fi,j+fi+1,j+1+wx+1,j+wy+1,j+1≤fi,j+1+fi+1,j+wx+1,j+wy+1,j+1 约掉了：
f
i
,
j
+
f
i
+
1
,
j
+
1
≤
f
i
,
j
+
1
+
f
i
+
1
,
j
{f_{i,j}+f_{i+1,j+1}}\leq {f_{i,j+1}}+{f_{i+1,j}}
fi,j+fi+1,j+1≤fi,j+1+fi+1,j 证毕。（另一种情况同理）
证明决策单调性： 打出表来会知道决策单调性是
p
i
−
1
,
j
≤
p
i
,
j
≤
p
i
,
j
+
1
p_{i-1,j}\leq p_{i,j}\leq p_{i,j+1}
pi−1,j≤pi,j≤pi,j+1。 接下来证明左边，假设不成立，设
p
i
,
j
=
p
,
p
i
−
1
,
j
=
k
p_{i,j}=p,p_{i-1,j}=k
pi,j=p,pi−1,j=k，则：
p
<
k
p<k
p<k 先写出两个决策点在
f
i
−
1
,
j
f_{i-1,j}
fi−1,j意义下的最优性：
A
:
f
i
−
1
,
k
≤
f
i
−
1
,
p
A:f_{i-1,k}\leq f_{i-1,p}
A:fi−1,k≤fi−1,p 再写出我们期望它们在
f
i
,
j
f_{i,j}
fi,j意义下的最优性：
B
:
f
i
,
k
≤
f
i
,
p
B:f_{i,k}\leq f_{i,p}
B:fi,k≤fi,p 设
A
+
T
=
B
A+T=B
A+T=B，用还原不等式的方法会发现，
T
T
T恰为四边形不等式，则
B
B
B得证。 因此
f
i
,
k
≤
f
i
,
p
,
f
i
,
k
≥
f
i
,
p
f_{i,k}\leq f_{i,p},f_{i,k}\geq f_{i,p}
fi,k≤fi,p,fi,k≥fi,p，则
f
i
,
k
=
f
i
,
p
f_{i,k}=f_{i,p}
fi,k=fi,p，说明
k
k
k与
p
p
p在
f
i
,
j
f_{i,j}
fi,j意义上一样优。因此决策单调性得证。
首先考虑考虑设状态： 二叉搜索树的一个子树对应有序序列上一个连续的区间，因为中序遍历要递增。所以一眼区间dp。考虑到贡献与层数有关，我们需要把状态写进层数： 设
f
k
,
i
,
j
f_{k,i,j}
fk,i,j表示目前区域根节点深度为
k
k
k，区间为
[
i
,
j
]
[i,j]
[i,j]的最小贡献。 这个dp很明显是
O
(
n
4
)
O(n^4)
O(n4)的，但是十秒钟…也可以过。
但是今天说的是四边形不等式优化dp。 我们首先考虑一下如何把状态优化为
O
(
n
2
)
O(n^2)
O(n2)，一般来说牵扯到因为贡献计算而需要增加状态维数的问题，主要有三种计算费用的方法：
费用推迟计算，主要的想法是从
i
,
j
i,j
i,j转移的贡献只与
i
,
j
i,j
i,j有关，与
k
k
k无关，那我们可以等到转移的时候从后继计算贡献。 （不过好像这么简单的技巧应该不需要总结）
因此设
f
i
,
j
f_{i,j}
fi,j表示区间
[
i
,
j
]
[i,j]
[i,j]构成了一颗子树，且假设根深度为
0
0
0时的贡献，则可以写出转移，转移就是枚举选择
k
k
k为根：
f
i
,
j
=
min
k
=
i
j
{
f
i
,
k
−
1
+
f
k
+
1
,
j
+
w
k
(
i
,
j
)
}
f_{i,j}=\overset{j}{\underset{k=i}\min}\{f_{i,k-1}+f_{k+1,j}+w_k(i,j)\}
fi,j=k=iminj{fi,k−1+fk+1,j+wk(i,j)}
设数字用
a
a
a表示，
s
s
s表示
a
a
a的前缀和，则其中贡献函数
w
k
(
i
,
j
)
=
s
j
−
s
i
−
1
+
a
k
w_k(i,j)=s_j-s_{i-1}+a_k
wk(i,j)=sj−si−1+ak
时间复杂度
O
(
n
3
)
O(n^3)
O(n3)，足够通过本题了，但是还可以做到更优。
打表打出决策单调性，
p
i
,
j
−
1
≤
p
i
,
j
≤
p
i
+
1
,
j
p_{i,j-1}\leq p_{i,j}\leq p_{i+1,j}
pi,j−1≤pi,j≤pi+1,j，可以优化为
O
(
n
2
)
O(n^2)
O(n2)
证明状态函数满足四边形不等式： 设
p
i
,
j
+
1
=
x
,
p
i
+
1
,
j
=
y
p_{i,j+1}=x,p_{i+1,j}=y
pi,j+1=x,pi+1,j=y，则：
{
f
i
,
j
≤
f
i
,
x
−
1
+
f
x
+
1
,
j
+
w
x
(
i
,
j
)
f
i
+
1
,
j
+
1
≤
f
i
+
1
,
y
−
1
+
f
y
+
1
,
j
+
1
+
w
y
(
i
+
1
,
j
+
1
)
f
i
,
x
−
1
+
f
x
+
1
,
j
+
1
+
w
x
(
i
,
j
+
1
)
=
f
i
,
j
+
1
f
i
+
1
,
y
−
1
+
g
y
+
1
,
j
+
w
y
(
i
+
1
,
j
)
=
f
i
+
1
,
j
\left\{\begin{matrix} f_{i,j}\leq f_{i,x-1}+f_{x+1,j}+w_x(i,j)\hspace{2.4cm}\\ f_{i+1,j+1}\leq f_{i+1,y-1}+f_{y+1,j+1}+w_y(i+1,j+1)\\ f_{i,x-1}+f_{x+1,j+1}+w_x(i,j+1)=f_{i,j+1}\hspace{1.2cm}\\ f_{i+1,y-1}+g_{y+1,j}+w_y(i+1,j)=f_{i+1,j}\hspace{1.25cm} \end{matrix}\right.
⎩⎨⎧fi,j≤fi,x−1+fx+1,j+wx(i,j)fi+1,j+1≤fi+1,y−1+fy+1,j+1+wy(i+1,j+1)fi,x−1+fx+1,j+1+wx(i,j+1)=fi,j+1fi+1,y−1+gy+1,j+wy(i+1,j)=fi+1,j 加起来：
f
i
,
j
+
f
i
+
1
,
j
+
1
+
f
x
+
1
,
j
+
1
+
g
y
+
1
,
j
+
w
x
(
i
,
j
+
1
)
+
w
y
(
i
+
1
,
j
)
≤
f
i
,
j
+
1
+
f
i
+
1
,
j
+
f
x
+
1
,
j
+
f
y
+
1
,
j
+
1
+
w
x
(
i
,
j
)
+
w
y
(
i
+
1
,
j
+
1
)
f_{i,j}+f_{i+1,j+1}+f_{x+1,j+1}+g_{y+1,j}+\textcolor{blue}{w_x(i,j+1)+w_y(i+1,j)}\leq f_{i,j+1}+f_{i+1,j}+f_{x+1,j}+f_{y+1,j+1}+\textcolor{red}{w_x(i,j)+w_y(i+1,j+1)}
fi,j+fi+1,j+1+fx+1,j+1+gy+1,j+wx(i,j+1)+wy(i+1,j)≤fi,j+1+fi+1,j+fx+1,j+fy+1,j+1+wx(i,j)+wy(i+1,j+1) 我们希望把贡献函数约掉，因此希望有这样一个不等式：
w
x
(
i
,
j
)
+
w
y
(
i
+
1
,
j
+
1
)
≤
w
x
(
i
,
j
+
1
)
+
w
y
(
i
+
1
,
j
)
\textcolor{red}{w_x(i,j)+w_y(i+1,j+1)} \leq \textcolor{blue}{w_x(i,j+1)+w_y(i+1,j)}
wx(i,j)+wy(i+1,j+1)≤wx(i,j+1)+wy(i+1,j) 这恰为贡献函数的四边形不等式，带入贡献函数的公式会发现显然成立。 剩下的部分就和石子合并的证明一样了，因此状态函数显然满足四边形不等式。
