【题解】P4767 [IOI2000]邮局

发表于 分类于 阅读次数： Valine：

题目链接（洛谷）

题目大意

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

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

你要编写一个程序，已知村庄数量\(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]\)中建一个邮局的最小代价。若村庄数为奇数，放中位数；若为偶数，放中间两数之间。

易得转移方程： \[ dp(i,j)=\min \{dp(k,j-1)+w(k+1,i)\},k\in[0,i) \] 时间复杂度\(O(PV^3)\)

预处理优化

用\(O(V^2)\)的时间复杂度预处理出\(w(l,r)\): \[ w(l,r)=w(l,r-1)+x(r)-x(\lfloor \frac{l+r}{2}\rfloor) \] 时间复杂度\(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;
}