题目链接

题目描述&＃xff1a;
建邮局&＃xff0c;每个村庄会到最近的邮局去寄信&＃xff0c;要求村庄到邮局的总距离最小

分析&＃xff1a;
假设要在[l,r][l,r]村庄中建一个邮局&＃xff0c;要使代价最小&＃xff0c;那么村庄一定建在第l&＃43;r2l&＃43;r2个村庄&＃xff08;中位数的知识&＃xff09;

我们预处理出w(l,r)w(l,r)&＃xff0c;表示在[l,r][l,r]建一座邮局的花费
于是就有递推式&＃xff1a;
w(l,r)&＃61;w(l,r−1)&＃43;dis[r]−dis[l&＃43;r2]w(l,r)&＃61;w(l,r−1)&＃43;dis[r]−dis[l&＃43;r2]
&＃xff08;在递推的时候&＃xff0c;中点最多向后移动一个&＃xff0c;而[l,r−1][l,r−1]到达新中点的距离之和不变&＃xff09;

设计方程f[i][j]f[i][j]&＃xff0c;表示在前ii个村庄建立j" role="presentation" >j$j$个邮局的最小花费
于是有dp转移方程&＃xff1a;
f[i][j]&＃61;min(f[k][j−1]&＃43;w(k&＃43;1,i))f[i][j]&＃61;min(f[k][j−1]&＃43;w(k&＃43;1,i))

感觉好像可以用斜率优化
然而这道题实际上可以用四边形不等式优化

这个式子是满足决策单调性的&＃xff0c;四边形不等式优化可以使时间复杂度从O(n3)O(n3)降到O(n2).O(n2).

我们怎么判断式子是否有决策单调性呢

给出相关的定理&＃xff1a;

• 对于函数w[i][j]w[i][j]&＃xff0c;若w[i][j]&＃43;w[i&＃43;1][j&＃43;1]<&＃61;w[i][j&＃43;1]&＃43;w[i&＃43;1][j]w[i][j]&＃43;w[i&＃43;1][j&＃43;1]<&＃61;w[i][j&＃43;1]&＃43;w[i&＃43;1][j]
  则ww满足凸多边形不等式（交叠的小于等于包含）


• 对于函数w[i][j]" role="presentation" >w[i][j]$w[i][j]$&＃xff0c;若w[a,b]<&＃61;w[c,d](c<&＃61;a<&＃61;b<&＃61;dw[a,b]<&＃61;w[c,d](c<&＃61;a<&＃61;b<&＃61;d&＃xff0c;那么我们称ww关于区间包含状态单调

定理1：w满足凸多边形不等式和区间包含状态单调，那么dp也满足四边形不等式

定理2：最优决策k[i][j]" role="presentation" >k[i][j]$k[i][j]$满足k[i][j−1]<&＃61;k[i][j]<&＃61;k[i&＃43;1][j]k[i][j−1]<&＃61;k[i][j]<&＃61;k[i&＃43;1][j]
这是四边形不等式优化dp的关键&＃xff0c;利用这个定理可以每次缩小kk的枚举范围，可以使时间复杂度从O(n3)" role="presentation" >O(n3)$O(n^3)$降到O(n2)O(n2)

定理3&＃xff1a;ww为凸当且仅当w[i][j]+w[i+1][j+1]<=w[i+1][j]+w[i][j+1]" role="presentation" >w[i][j]+w[i+1][j+1]<=w[i+1][j]+w[i][j+1]$w[i][j]+w[i+1][j+1]<=w[i+1][j]+w[i][j+1]$

定理3其实告诉我们验证ww是否为凸的方法：
固定一个变量，看成是一个一元函数，进而判断单调性
如，我们可以固定j" role="presentation" >j$j$算出w[i][j&＃43;1]−w[i][j]w[i][j&＃43;1]−w[i][j]关于ii的表达式，如果关于i" role="presentation" >i$i$是递减&＃xff0c;则ww为凸

在实际的应用中我们往往不能用数学方法证明w" role="presentation" >w$w$为凸&＃xff0c;不过我们可以通过打表找规律的方法来发现dp的决策单调性

tip

注意循环的顺序
还是我们的原则&＃xff1a;从稳定状态转移
因为我们在转移的时候会用到s[i−1][j]s[i−1][j]&＃xff0c;所以第一维需要从11到n" role="presentation" >n$n$循环
还会用到s[i][j&＃43;1]s[i][j&＃43;1]&＃xff0c;所以第二维需要从nn到1" role="presentation" >1$1$循环

#include
#include
#includeusing namespace std;const int N&＃61;305;
const int INF&＃61;1e9;
int f[30][N],w[N][N],s[30][N],dis[N],n,m;void prepare() {for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) {w[i][i]&＃61;0;for (int j&＃61;i&＃43;1;j<&＃61;n;j&＃43;&＃43;) {w[i][j]&＃61;w[i][j-1]&＃43;dis[j]-dis[(i&＃43;j)/2];}}
}int main() {scanf("%d%d",&n,&m);for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) scanf("%d",&dis[i]);prepare();for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) f[1][i]&＃61;w[1][i],s[1][i]&＃61;0;for (int i&＃61;2;i<&＃61;m;i&＃43;&＃43;) {s[i][n&＃43;1]&＃61;n;for (int j&＃61;n;j>i;j--) {f[i][j]&＃61;INF;for (int k&＃61;s[i-1][j];k<&＃61;s[i][j&＃43;1];k&＃43;&＃43;) if (f[i][j]>f[i-1][k]&＃43;w[k&＃43;1][j]) {f[i][j]&＃61;f[i-1][k]&＃43;w[k&＃43;1][j];s[i][j]&＃61;k;}}}printf("%d",f[m][n]);return 0;
}