luogu_P4767 [IOI2000]邮局

传送门

Description

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

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

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

Solution

大概是把dp的常见优化的经典练习题都打了一波。

这是四边形不等式优化的题目。证明？百度百科上就很不错了，就不说了。

满足\(f[i][j]\) 的决策点会在\(f[i][j-1]\)和\(f[i+1][j]\)的决策点之间

Code

#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
#define MN 3005
#define mN 305
int V,P,a[MN],f[MN][mN],q[MN],d[MN][MN],g[MN][mN];
inline int dis(int l,int r)
{
    if(d[l][r]) return d[l][r];
    else return d[l][r]=q[r]+q[l-1]-q[(l+r)>>1]-q[(l+r-1)>>1];
}
int main()
{
    V=read();P=read();
    memset(f,0x3f,sizeof f);
    register int i,j,k;
    for(i=1;i<=V;++i) a[i]=read(),q[i]=q[i-1]+a[i];
    std::sort(a+1,a+V+1);

    for(i=1;i<=V;++i) f[i][1]=dis(1,i);

    for(g[V+1][k=2]=V;k<=P;++k,g[V+1][k]=V)
        for(i=V;i>=1;--i)for(j=g[i][k-1];j<=g[i+1][k];++j)
            if(f[j][k-1]+dis(j+1,i)<f[i][k])
                f[i][k]=f[j][k-1]+dis(j+1,i),g[i][k]=j;
    return 0*printf("%d\n",f[V][P]);
}

Blog来自PaperCloud，未经允许，请勿转载，TKS！