[IOI2000] 邮局

题目描述

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

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

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

\(n\le 5\times 10^5\)

1. \(n\le 300\)

定义 \(dp_{i,j}\) 为前 \(i\) 个村庄，用了 \(j\) 个邮局的最小距离可能。
我们把那些最近的邮局为同一个的称为一段，那么我们可以枚举上一段的开头。
对于某一段 \([l,r]\) ,邮局一定是放在中位数那里，然后预处理 \(a\) 的前缀和就可以了。

2. \(n\le 3000\)

观察到那个式子是由决策单调性的，所以可以用二维决策单调性优化。

换一下，定义 \(dp_{i,j}\) 为用了 \(i\) 个邮局，前 \(j\) 个村庄的最小值，\(p_{i,j}\) 为他的最优决策点是 \(dp_{i,p_{i,j}}\) 转移过来。那么一定满足 \(p_{i-1,j}<p_{i,j}\le p_{i,j+1}\)，那么可以只在这个区间内扫描。均摊复杂度 \(O(n^2)\)

#include<bits/stdc++.h>
using namespace std;
const int N=3005,M=305;
typedef long long LL;
int read()
{
	int s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9')
		s=s*10+ch-48,ch=getchar();
	return s;
}
int n,a[N],m,p[M][N];
LL dp[M][N],s[N];
LL ask(int l,int r)
{
	int md=l+r>>1;
	return s[r]-s[md]-1LL*(r-md)*a[md]+(md-l+1LL)*a[md]-s[md]+s[l-1];
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		s[i]=s[i-1]+(a[i]=read());
	sort(a+1,a+n+1);
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int i=1;i<=m;i++)
	{
		p[i][n+1]=n;
		for(int j=n;j>=1;j--)
			for(int k=max(p[i-1][j],1);k<=p[i][j+1]&&k<=j;k++)
				if(dp[i-1][k-1]+ask(k,j)<dp[i][j])
					p[i][j]=k,dp[i][j]=dp[i-1][k-1]+ask(k,j);
	}
	printf("%lld",dp[m][n]);
	return 0;
			
}

3.$ n\le 5\times 10^5$

要选严格 \(k\) 个邮局，想到 WQS 二分。打表可知函数是凸的。

然后方程变成 1 维，可以知道这个是满足决策单调性的，二分队列即可。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int l=0,r=1000000000,n,m,a[N],c[N];
long long dp[N],s[N];
struct node{
	int l,r,x;
}q[N];
long long ask(int l,int r)
{
	int md=l+r>>1;
	return dp[l-1]+s[r]-s[md]-1LL*(r-md)*a[md]+(md-l+1LL)*a[md]-s[md]+s[l-1];
}
int erfen(int x,int y,int l,int r)//x 
{
	++r;
	while(l<=r)
	{
		int md=l+r>>1;
		if(ask(x,md)>=ask(y,md))
			l=md+1;
		else
			r=md-1;
	}
	return l;
}
int ok(int x)
{
	int l,r;
	memset(dp,0x7f,sizeof(dp));
	memset(c,0,sizeof(c));
	q[l=r=1]=(node){1,n,1};
	dp[0]=0;
	for(int i=1;i<=n;i++)
	{
		if(q[l].r==i-1)
			++l;
		dp[i]=ask(q[l].x,i)+x;
		c[i]=c[q[l].x-1]+1;
		q[l].l=i;
		if(l>r||ask(i+1,q[r].r)<ask(q[r].x,q[r].r))
		{
			while(l<=r&&ask(i+1,q[r].l)<ask(q[r].x,q[r].l))
				--r;
			int k=erfen(i+1,q[r].x,q[r].l,q[r].r);
			q[r].r=k-1;
			q[++r]=(node){k,n,i+1};
		}
	}
	return c[n]<=m;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i),s[i]=s[i-1]+a[i];
	while(l<=r)
	{
		int md=l+r>>1;
		if(ok(md))
			r=md-1;
		else
			l=md+1;
	}
	ok(l);
	printf("%d",dp[n]-m*l);	
}