【题解】P4767 [IOI2000]邮局

发表于 分类于 阅读次数： Valine： 本文字数： 938 阅读时长 ≈ 3 分钟

题目链接（洛谷）

题目大意

高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。

邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。

你要编写一个程序，已知村庄数量$V$、位置$x$和邮局的数量$P$。计算每个村庄和最近的邮局之间所有距离的总和的最小可能。

$1\le P \le 300,P\le V\le 3000,1\le$村庄位置$\le 10000$

分析

基本方法

设$dp(i,j)$表示前$i$个村庄放$j$个邮局的最小距离和；$w(i,j)$表示在区间$[i,j]$中建一个邮局的最小代价。若村庄数为奇数，放中位数；若为偶数，放中间两数之间。

易得转移方程：

时间复杂度$O(PV^3)$

预处理优化

用$O(V^2)$的时间复杂度预处理出$w(l,r)$:

时间复杂度$O(PV^2)$

四边形不等式优化

区间包含关系单调性：对于任意$l\le l’\le r’\le r$， 均有$w(l’,r′)\le w(l,r)$，则称函数$w$区间包含关系具有单调性。

四边形不等式：对于任意$l_1\le l_2\le r_1\le r_2$，均有$w(l_1,r_1 )+w(l_2,r_2 )\le w(l_1,r_2 )+w(l_2,r_1 )$成立，则称函数$w$满足四边形不等式。

引理：若$w(l,r)$满足区间包含单调性和四边形不等式，则状态$f(i,j)$满足四边形不等式。

定理：若状态$f$满足四边形不等式，记$d(i,j)$为$f(i,j)$的最优决策点，则有：$d(i,j-1)\le d(i,j)\le d(i+1,j)$。

回到本题，由定义，$w$显然满足区间包含关系单调性。

由$w$的递推式：$w(l,r)=w(l,r-1)+x(r)-x(\lfloor \frac{l+r}{2}\rfloor)$，可得：

$w(l,r+1)-w(l,r)=x(r+1)-x(\lfloor \frac{l+r+1}{2}\rfloor)~①$

$w(l+1,r+1)-w(l+1,r)=x(r+1)-x(\lfloor \frac{l+r+2}{2}\rfloor)~②$

$①-②$ 左边$=x(\lfloor \frac{l+r+2}{2}\rfloor)-x(\lfloor \frac{l+r+1}{2}\rfloor)$

$\because x$递增 $\therefore$ 右边$x\ge 0$

$\therefore$ 左边 $=w(l,r+1)-w(l,r)-w(l+1,r+1)+w(l+1,r)\ge 0$

$\therefore w(l,r)+w(l+1,r+1)\le w(l,r+1)+w(l+1,r)$

$\therefore w$ 满足四边形不等式，所以$dp$满足四边形不等式，所以对于$dp(i,j)$的最优决策下标 $d(i,j)$，有 $d(i,j-1)≤d(i,j)≤d(i+1,j)$，我们在转移时，从$d(i,j-1)$到$d(i+1,j)$中找最优决策。要注意因为用到了$i+1$，需要倒序枚举。

时间复杂度$O(PV)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
int v,p,x[3005],dp[3005][305],w[3005][3005],d[3005][305];
int main(){
    cin>>v>>p;
    for(int i=1;i<=v;i++) cin>>x[i];
    for(int l=1;l<=v;l++){
        w[l][l]=0;
        for(int r=l+1;r<=v;r++){
            w[l][r]=w[l][r-1]+x[r]-x[(int)(l+r)/2];
        }
    }
    sort(x+1,x+p+1);
    memset(dp,0x3f,sizeof dp);
    dp[0][0]=0;
    for (int j=1;j<=p;j++){
        d[v+1][j]=v;//边界
        for (int i=v;i>=1;i--){
            int minn=0x3f3f3f3f,id;
            for(int k=d[i][j-1];k<=d[i+1][j];k++){
                if(dp[k][j-1]+w[k+1][i]<minn){
                    minn=dp[k][j-1]+w[k+1][i];
                    id=k;
                }
            }
            dp[i][j]=minn;
            d[i][j]=id;
        }
    }
    cout<<dp[v][p];
    return 0;
}