【IOI2000】Post Office

我不想打表，所以我证明了这道题的四边形不等式。

$w_{a,d}$表示区间$[a,d]$建一个邮局的最小代价，也就是选择中位数。

首先证明$a\le b\le c \le d,w_{a,d}\ge w_{b,c}$

这个不难，若$a<b\le c<d$，这是成立的，因为在中位数左边，右边均多了数，也就是代价增加了。

若$a=b\le c\le d$，$w_{a,d},w_{a,c}$，若中位数发生改变，那么也就是$mid$向右发生偏移，那么在左边的个数多了一个，而右边个数至少也是原来的，总的代价多了一个偏移量，因此$w_{a,d}\ge w_{a,c}$

中位数向左发生偏移是类似的。

因此$a\le b\le c \le d,w_{a,d}\ge w_{b,c}$。

下面$a\le b\le c\le d,w_{a,d}+w_{b,c}\ge w_{a,c}+w_{b,d}$，接下来，只证明$a<b,w_{a,b+1}+w_{a+1,b}\ge w_{a,b}+w_{a+1,b+1}$。

对于$w_{a,b+1},w_{a+1,b}$，它们的中位数是相等的，记中位数为$mid_1$。

那么有$w_{a,b+1}+w_{a+1,b}=2*w_{a+1,b}+d_{b+1}-d_{mid_1}+d_{mid_1}-d_{a}$

$\because w_{a,b}\le w_{a+1,b}+d_{mid_1}-d_a,w_{a+1,b+1}\le w_{a+1,b}+d_{b+1}-d_{mid_1}$

$w_{a,b+1}+w_{a+1,b}\ge w_{a,b}+w_{a+1,b+1}$

证毕。

之后就是一些常规操作了。

对于$a<c$，$w_{a,c+1}+w_{a+1,c}\ge w_{a,c}+w_{a+1,c+1}$

对于$a<c+1$，$w_{a+1,c+1}+w_{a+2,c}\ge w_{a+1,c}+w_{a+2,c+1}$

两式相加，有

$w_{a,c+1}+w_{a+1,c}+w_{a+1,c+1}+w_{a+2,c}\ge w_{a,c}+w_{a+1,c+1}+w_{a+1,c}+w_{a+2,c+1}$

减掉重的部分，有

$w_{a,c+1}+w_{a+2,c}\ge w_{a,c}+w_{a+2,c+1}$

以此类推，有

$a\le b\le c,w_{a,c+1}+w_{b,c}\ge w_{a,c}+w_{b,c+1}$

$a\le b\le c\le d,w_{a,d}+w_{b,c}\ge w_{a,c}+w_{b,d}$

之后就是推$f$也是一个四边不等式，证明

$\large f_{i,j+1}+f_{i+1,j}\ge f_{i,j}+f_{i+1,j+1}$。

先明确一下$f$的定义，$f_{i,j}$表示前$i$个村庄共有$j$个邮局的最小代价。

$DP$推推得：

$f_{i,j}=\min\{f_{k,j-1}+w_{k+1,i}\}$

证明$j=1$的情况。

$f_{i,2}+f_{i+1,1}\ge f_{i,1}+f_{i+1,2}$

$f_{i,2}+w_{1,i+1}\ge f_{i+1,2}+w_{1,i}$

设$f_{i,2}$的最优决策为$p(0<p<i)$,即$f_{i,2}=w_{1,p}+w_{p+1,i}$

还有$f_{i+1,2}$的最优决策可能不为$p$，即$f_{i+1,2}\le w_{1,p}+w_{p+1,i+1}$

四边形不等式,
$w_{1,i+1}+w_{p+1,i}\ge w_{1,i}+w_{p+1,i+1}$

有$w_{1,i+1}+w_{1,p}+w_{p+1,i}\ge w_{1,i}+w_{1,p}+w_{p+1,i+1}$

因此
$f_{i,2}+f_{i+1,1}=w_{1,i+1}+w_{1,p}+w_{p+1,i}\ge w_{1,i}+w_{1,p}+w_{p+1,i+1}\ge f_{i,1}+f_{i+1,2}$

之后数学归纳法即可，已经比打表法好多！。

之后证明一下决策单调性

简记$p_{i,j}$为令$f_{i,j}$取到最小值的$k$值，那么$p_{i,j-1}\le p_{i,j}\le p_{i+1,j}$

证明:

记$p=p_{i,j}$，那么对于$\forall k\le p$，因为$f$满足四边形不等式，则有

$f_{p,j-1}+f_{k,j}\ge f_{k,j-1}+f_{p,j}$

$f_{k,j}-f_{p,j}\ge f_{k,j-1}-f_{p,j-1}$

因为$p$的最优性，那么$f_{k,j-1}+w_{k+1,i}\ge f_{p,j-1}+w_{p+1,i}$
因此$(f_{k,j}+w_{k+1,i})-(f_{p,j}+w_{p+1,i})=f_{k,j}+w_{k+1,i}-f_{p,j}-w_{p+1,i}\ge f_{k,j-1}-f_{p,j-1}+w_{k+1,i}-w_{p+1,i}\ge 0$

因此$f_{k,j}+w_{k+1,i}\ge f_{p,j}+w_{p+1,i}$

所以对于$f_{i,j}$来说，$p$优于任何的$k\le p$。因此$p_{i,j}\ge p_{i,j-1}$

同理，$p_{i,j}\le p_{i+1,j}$

证毕。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define gc getchar()
using namespace std;
const int P=305,N=3005;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int f[N][P],s[N],a[N],p[N][P];
inline int calc(int l,int r)
{
    int mid=l+r+1>>1;
    return a[mid]*(mid-l+1)-(s[mid]-s[l-1])+(s[r]-s[mid])-a[mid]*(r-mid);
}
int main()
{
    int n,m;qr(n),qr(m);
    for(int i=1;i<=n;i++)qr(a[i]),s[i]=s[i-1]+a[i];
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)f[i][1]=calc(1,i);
    for(int i=1;i<=m;i++)p[n][i]=1;
    for(int j=2;j<=m;j++)
    {
        p[n+1][j]=n;int tmp=0x3f3f3f3f;
        for(int i=n;i>=1;i--)
            for(int k=p[i][j-1];k<=p[i+1][j];k++)
                if((tmp=f[k][j-1]+calc(k+1,i))<f[i][j])
                {
                    f[i][j]=tmp;
                    p[i][j]=k;
                }
    }
    qw(f[n][m]);puts("");
    return 0;
}

手机上阅读