【IOI2000】邮局

_Sein · 2019-10-24 16:09:11 · 题解

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

首先证明$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也是一个四边不等式，证明

先明确一下$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;
}