P4767 [IOI2000] 邮局加强版

XichenOC · 2024-11-15 17:07:47 · 题解

P4767 [IOI2000] 邮局加强版

双倍经验P10967 [IOI2000] 邮局（原始版）

题目翻译：

给定村庄数量v和邮局数量p求如何放置邮局才能使每个村庄到邮局的距离和最小

思路：

法一： 我们可以很快看出一个关系，令dp[i][j]表示前i个村庄放置j个邮局的最小值，那可以得出一个最简单的转移方程：

dp[i][j]=\min_{k=0}^{k<i}dp[k][j-1]+w[k+1][i]

若直接枚举所有的i,j,k，那复杂度就到了O(pv^3)

法二： 我们考虑优化，可以发现w[i][j]可以以O(v^2)预处理出来，因为要使一段区间的所有点到某一点的距离和最小，那这个点一定在最中间，再加上规律，就可以得到：

w[i][j]=w[i][j-1]+x[i]-x[\lfloor\frac {i+j}{2}\rfloor]

因此其转移可以优化到O(pv^2)

法三： 继续考虑优化，我们可以发现w[i][j]满足四边形不等式，原因如下:

考虑转换，令 j=j+1
w[i][j+1]-w[i][j]=x[i]-x[\lfloor \frac{i+j+1}{2}\rfloor]
令i=i+1,j=j+1，则有
w[i+1][j+1]-w[i+1][j]=x[i+1]-x[\lfloor \frac{i+j+2}{2}\rfloor]
联立两式,使一式减二式：
w[i][j+1]-w[i][j]-(w[i+1][j+1]-w[i+1][j])=x[i]-x[\lfloor \frac{i+j+1}{2}\rfloor]-(x[i+1]-x[\lfloor \frac{i+j+2}{2}\rfloor])
化简可得：
x[\lfloor \frac{i+j+2}{2}\rfloor]-x[\lfloor \frac{i+j+1}{2}\rfloor]=0
由于x的坐标单调递增，则有：
x[\lfloor \frac{i+j+2}{2}\rfloor]-x[\lfloor \frac{i+j+1}{2}\rfloor] \geq 0
及
w[i+1][j]-w[i+1][j+1]-(w[i][j]-w[i][j+1]) \le 0
转换位置得：
w[i+1][j]+w[i][j+1] \le w[i][j]+w[i+1][j+1]
则 \forall {a \le b \le c \le d}，满足 w[a][d] \geq w[b][c] 可知w[i][j]满足四边形不等式，则dp[i][j]也满足四边形不等式

由次可知，对于dp[i][j]的最优解dp[i][j-1] \le dp[i][j] \le dp[i+1][j]
我们只需要在转移时在区间[dp[i][j-1],dp[i+1][j]]中找，复杂度变为O(pv)

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3010;
int x[N],dp[N][N],w[N][N],d[N][N];
int main(){
    int v,p;
    cin>>v>>p;
    for(int i=1;i<=v;i++)cin>>x[i];
    for(int i=1;i<=v;i++){
        w[i][i]=0;
        for(int j=i+1;j<=v;j++){
            w[i][j]=w[i][j-1]+x[j]-x[(i+j)>>1];
        }
    }
    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 mn=INT_MAX,minn;
            for(int k=d[i][j-1];k<=d[i+1][j];k++){
                if(dp[k][j-1]+w[k+1][i]<mn){
                    mn=dp[k][j-1]+w[k+1][i];
                    minn=k;
                }
            }
            dp[i][j]=mn;
            d[i][j]=minn;
        }
    }
    cout<<dp[v][p]<<endl;
}

P4767 [IOI2000] 邮局 加强版