IOI2000 邮局 加强版 题解

考虑动态规划，设 $f_{i,j}$ 为经过了 $i$ 个村庄，正在建第 $j$​ 个邮局的最优距离。

以及 $w_{i,j}$ 表示区间 $[i,j]$​ 内建一个邮局时的距离总和。

$a$ 数组表示每个村庄的坐标编号。

朴素版状态转移方程：
$$\begin{gathered} f_{i,j}=\min (f_{i,j},f_{k,j-1}+w_{k+1,i}) \\ k\in [0,i) \end{gathered}$$
根据初一上册数学，可知在区间 $[x,y]$ 中距离所有点的距离之和最短的点为：

若 $2\mid x+y$，则点位于 $\lfloor \frac{x+y}{2}\rfloor$。

反之位于 $\lfloor \frac{x+y+1}{2}\rfloor$。

注意到，上述状态转移方程，有三个未知数：$i,j,k$。可得时间复杂度为 $O(P{V}^3)$，肯定过不了。

考虑四边形不等式优化。

注意到，$w$​ 函数的状态转移方程为：
$$w_{l,r+1}=w_{l+r}+a_{r+1}-a_{\lfloor \frac{l+r+1}{2}\rfloor }$$
需要简化，过程如下，虽复杂，但重要，可加以理解。
$$\{\begin{array}{l}{w}_{l,r+1}=w_{l+r}+a_{r+1}-a_{\lfloor \frac{l+r+1}{2}\rfloor }1式\\ w_{l+1,r+1}=w_{l+1,r}+a_{r+1}-a_{\lfloor \frac{l+r+2}{2}\rfloor }2式\end{array}$$
2式 $-$ 1式，得：
$$\begin{gathered} w_{l+1,r+1}-w_{l,r+1}=w_{l+1,r}+a_{r+1}-a_{\lfloor \frac{l+r+2}{2}\rfloor }-w_{l,r}-a_{r+1}+a_{\lfloor \frac{l+r+1}{2}\rfloor } \\ {w}_{l+1,r+1}-w_{l,r+1}=w_{l+1,r}-w_{l,r}+a_{\lfloor \frac{l+r+1}{2}\rfloor }-a_{\lfloor \frac{l+r+2}{2}\rfloor } \\ {w}_{l+1,r+1}-w_{l,r+1}-w_{l+1,r}+w_{l,r}=a_{\lfloor \frac{l+r+1}{2}\rfloor }-a_{\lfloor \frac{l+r+2}{2}\rfloor } \end{gathered}$$
$\because$ 坐标单调上升
$$\begin{gathered} \therefore a_{\lfloor \frac{l+r+1}{2}\rfloor }\le a_{\lfloor \frac{l+r+2}{2}\rfloor } \\ \therefore a_{\lfloor \frac{l+r+1}{2}\rfloor }-a_{\lfloor \frac{l+r+2}{2}\rfloor }\le 0 \\ {w}_{l+1,r+1}-w_{l,r+1}-w_{l+1,r}+w_{l,r}\le 0 \\ {w}_{l,r}+w_{l+1,r+1}\le w_{l,r+1}+w_{l,r+1} \\ {w}_{l,r+1}+w_{l+1,r}\ge w_{l,r}+w_{l+1,r+1} \end{gathered}$$
通过四边形不等式可知，若 $a,b,c,d$ 满足 $a\le b\le c\le d$，且 $w_{a,c}+w_{b,d}\le w_{a,d}+w_{b,d}$，则称 $w$ 为四边形不等式，可以优化时间复杂度。

$\because l\le l+1\le r\le r+1$，则可以将 $a,b,c,d$​ 分别带入进去，即：

当 $a=l,b=l+1,c=r,d=r+1$ 时：
$$\begin{gathered} w_{l,r+1}+w_{l+1,r}\ge w_{l,r}+w_{l+1,r+1} \\ {w}_{a,c}+w_{b,d}\ge w_{a,d}+w_{b,d} \end{gathered}$$
再附上1式 $-$ 2式的：
$$\begin{gathered} w_{l,r+1}-w_{l+1,r+1}=w_{l,r}-a_{r+1}-a_{\lfloor \frac{l+r+1}{2}\rfloor }-w_{l+1,r}+a_{r+1}+a_{\lfloor \frac{l+r+2}{2}\rfloor } \\ {w}_{l,r+1}-w_{l+1,r+1}=w_{l,r}-a_{\lfloor \frac{l+r+1}{2}\rfloor }-w_{l+1,r}+a_{\lfloor \frac{l+r+2}{2}\rfloor } \\ {w}_{l,r+1}-w_{l+1,r+1}-w_{l,r}+w_{l+1,r}=a_{\lfloor \frac{l+r+2}{2}\rfloor }-a_{\lfloor \frac{l+r+1}{2}\rfloor } \end{gathered}$$
$\because$ 坐标单调上升
$$\begin{gathered} \therefore a_{\lfloor \frac{l+r+2}{2}\rfloor }\ge a_{\lfloor \frac{l+r+1}{2}\rfloor } \\ {a}_{\lfloor \frac{l+r+2}{2}\rfloor }-a_{\lfloor \frac{l+r+1}{2}\rfloor }\ge 0 \\ {w}_{l,r+1}+w_{l+1,r}-w_{l+1,r+1}-w_{l,r}\ge 0 \\ {w}_{l,r+1}+w_{l+1,r}\ge w_{l+1,r+1}+w_{l,r} \end{gathered}$$

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXV=3003,MAXP=305,inf=1e9+5;
int v,p;
int f[MAXV][MAXP];//经过了i个村庄，正在建j个邮局 
int a[MAXV],w[MAXV][MAXV],dp[MAXV][MAXP];
int minn,minid;
signed main(){scanf("%d%d",&v,&p);for(int i=1;i<=v;i++)scanf("%d",&a[i]);sort(a+1,a+v+1);memset(f,0x3f,sizeof(f));f[0][0]=0;for(int i=1;i<=v;i++)for(int j=i+1;j<=v;j++)w[i][j]=w[i][j-1]+a[j]-a[i+j>>1];for(int j=1;j<=p;j++){dp[v+1][j]=v;for(int i=v;i>=1;i--){minn=inf;for(int k=dp[i][j-1];k<=dp[i+1][j];k++){if(f[k][j-1]+w[k+1][i]<minn){minn=f[k][j-1]+w[k+1][i];minid=k;}}f[i][j]=minn;dp[i][j]=minid;}}			printf("%d\n",f[v][p]);return 0;
}