题解 P4767 【[IOI2000]邮局】

HoshiuZ · 2020-02-25 19:22:23 · 题解

思路

首先将坐标排个序。

定义dp[i][j]表示前i个村庄放j个邮局的前i个村庄的最小距离总和，w(i,j)表示村庄区间[i,j]内放一个村庄时该区间的最小距离总和。

易得

那么关键就在于w(k+1,i)的处理了。

基本的数学知识，若村庄数为奇数，放中位数处距离和最小。若村庄为偶数，放中间两个村庄之间任意一处均可。

于是便可得一个O(PV^3)的算法。

#include<bits/stdc++.h>
#define MAXN 3010
#define N 310

using namespace std;

int V,P,X[MAXN],dp[MAXN][N];

int w(int l,int r) {
    int mid=l+r>>1,ans=0;
    for(int i=l;i<mid;i++) ans+=X[mid]-X[i];
    for(int i=mid+1;i<=r;i++) ans+=X[i]-X[mid];
    return ans;
}

int main() {
    cin>>V>>P;
    for(int i=1;i<=V;i++) cin>>X[i];

    sort(X+1,X+V+1);
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int j=1;j<=P;j++) {
        for(int i=1;i<=V;i++) {
            for(int k=0;k<i;k++) {
                dp[i][j]=min(dp[k][j-1]+w(k+1,i),dp[i][j]);
            }
        }
    }

    cout<<dp[V][P]<<endl;

    return 0;
}

再想想，可以提前预处理出w，其实这个w是可以O(V^2)递推出来的，根据放置一个邮局，邮局位置总是在中位数处，便可推得

于是又可以得到一个O(PV^2)的算法。

#include<bits/stdc++.h>
#define MAXN 3010
#define N 310

using namespace std;

int V,P,X[MAXN],dp[MAXN][N],w[MAXN][MAXN];

void init() {
    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[l+r>>1];
        }
    }
}

int main() {
    cin>>V>>P;
    for(int i=1;i<=V;i++) cin>>X[i];

    init();
    sort(X+1,X+V+1);
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int j=1;j<=P;j++) {
        for(int i=1;i<=V;i++) {
            for(int k=0;k<i;k++) {
                dp[i][j]=min(dp[k][j-1]+w[k+1][i],dp[i][j]);
            }
        }
    }

    cout<<dp[V][P]<<endl;

    return 0;
}

其实w是满足四边形不等式的。

由上面w的递推式，可得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]\ ②

用①-②，得

即

因此w满足四边形不等式，且明显，对于a\le b\le c\le d，w[a][d]\ge w[b][c]，故dp满足四边形不等式。

因为dp满足四边形不等式，所以对于dp[i][j]的最优决策d[i][j]，d[i][j-1]\le d[i][j]\le d[i+1][j]

于是状态转移dp[i][j]时，从[d[i][j-1],d[i+1][j]]中找最优决策。

由于要用到dp[i+1][j]，所以倒序求解。

时间复杂度O(PV)。

代码

#include<bits/stdc++.h>
#define MAXN 3010
#define N 310
#define INF 0x3f3f3f3f

using namespace std;

int V,P,X[MAXN],dp[MAXN][N],w[MAXN][MAXN],d[MAXN][N];

void init() {
    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[l+r>>1];
        }
    }
}

int main() {
    cin>>V>>P;
    for(int i=1;i<=V;i++) cin>>X[i];

    init();
    sort(X+1,X+V+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=INF,minid;
            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];
                    minid=k;
                }
            }
            dp[i][j]=minn;
            d[i][j]=minid;
        }
    }

    cout<<dp[V][P]<<endl;

    return 0;
}