Description

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

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

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

Solution

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

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

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

Code

#include
    
     #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 305int 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)
    

---

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