我不想打表，所以我证明了这道题的四边形不等式。
$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;
}
0 条评论