P4767 IOI2000 邮局

有 (n) 个村庄，给出了他们的横坐标。现在要在这些村庄中的一些村庄安放 (p) 个邮局，要求算每个村庄和最近的邮局之间所有距离的最小可能的总和。

(50\%:sim70\%)

悄咪咪告诉你，开氧可以跑(90pts!!!!!!!!!!) 这还打啥正解

(f[i][j])表示前(i)个村庄放(j)个邮局最小距离和

(w[i][j])表示村庄区间([i,j])内放(1)个邮局的距离和

(w)可以预处理出来，放置一个邮局，邮局位置总是在中位数处

(w[l][r]=w[l][r-1]+X[r]-X[frac{l+r}2]) (V^2)递推

(f[i][j]=min{f[k][j-1]+w[k+1][j])}~~kin[0,i))

复杂度(O(PV^2))

const int N = 3005;
int V,P,x[N],w[N][N],f[N][305];
inline int min(int a,int b){return a < b ? a : b;}
void init(){
	for(re int i = 1;i <= V;++i) x[i] = read();
	for(re int i = 1;i <= V;++i)
		for(re int j = i+1;j <= V;++j)
			w[i][j] = w[i][j-1] + x[j] - x[i+j>>1];
}
int main(){
	V = read(); P = read();
	init();
	memset(f,0x3f,sizeof(f));
	f[0][0] = 0;
	for(re int j = 1;j <= P;++j)
		for(re int i = 1;i <= V;++i)
			for(re int k = 0;k < i;++k)
				f[i][j] = min(f[k][j-1] + w[k+1][i],f[i][j]);
	printf("%d",f[V][P]);
}

(100\%:)

(w)其实是满足四边形不等式的

由递推式可得(w[l][r+1]-w[l][r]=X[r+1]-X[frac{l+r+1}2]~~①)

[w[l+1][r+1]-w[l+1][r]=X[r+1]-X[frac{l+r+2}2]~~②\ ①-②\ =X[frac{l+r+2}2]-X[frac{l+r+1}2]\ ]

(X)递增，则(large X[frac{l+r+2}2]-X[frac{l+r+1}2]ge0)

即

[w[l][r+1]-w[l][r]-(w[l+1][r+1]-w[l+1][r])ge0\ w[l][r+1]-w[l][r]-w[l+1][r+1]+w[l+1][r]ge0\ w[l][r+1]+w[l+1][r]ge w[l][r]+w[l+1][r+1] ]

显然(w)满足四边形不等式，且对于(ale ble cle d)，(w[a][d]ge w[b][c])，(dp)满足四边形不等式

所以对于(f[i][j])决策，(f[i][j-1]le f[i][j]le f[i+1][j])

令(s[i][j])为(i)之前建(j)个邮局的最优决策

所以转移(f[i][j])时，从([s[i][j-1],s[i+1][j]])中找最优决策

因为要用到(f[i+1][j])，所以倒叙枚举(i)

(O(PV))

int V,P,x[N],w[N][N],f[N][305],s[N][305];
void init(){
	for(int i = 1;i <= V;++i) x[i] = read();
	for(int i = 1;i <= V;++i)
		for(int j = i+1;j <= V;++j)
			w[i][j] = w[i][j-1] + x[j] - x[i+j>>1];
}
int main(){
	V = read(); P = read();
	init();
	memset(f,0x3f,sizeof(f));
	f[0][0] = 0;
	for(int j = 1;j <= P;++j){
		s[V + 1][j] = V;
		for(int i = V;i >= 1;--i){ 
			int minn = 0x3f3f3f3f,minid;
			for(int k = s[i][j-1];k <= s[i+1][j];++k){
				if(f[k][j-1] + w[k+1][i] < minn){
					minn = f[k][j-1] + w[k+1][i];
					minid = k;
				}
			}
			f[i][j] = minn; s[i][j] = minid;	
		} 
	}
	printf("%d",f[V][P]);
}