Luogu P4767「IOI2000」邮局

P4767「IOI2000」邮局

显然 DP ,考虑设 \(f_{i,j}\) 表示前 \(j\) 个村庄放了 \(i\) 个邮局的最小距离,为了方便 DP ,我们钦定这个区间里的村庄都匹配这些邮局。

那么转移式写出来就是 :

\[f_{i,j} = \min_{k=1}^{j-1} \left\{ f_{i,k-1} + w(k+1,j) \right\} \]

其中, \(w(l,r)\) 表示区间 \(\left[ l,r \right]\) 中放一个邮局的贡献,由初中知识可知取最中间的村庄放置邮局一定最优。
那么就有:

\[w(l,r) = w(l,r-1) + X_{r} - X_{\lfloor \frac{l+r}{2} \rfloor} \]

显然, $ w $ 是满足四边形不等式和区间包含单调性的。

\[\text{设 } l_1 \le l_2 \le r_1 \le r_2 ,\\ \text{则 } w(l_1,r_1) + w(l_2,r_2) = \sum_{i=1}^{\lfloor \frac{l_1+r_1}{2} \rfloor} \left( X_{r_1-i+1} - X_{i} \right) + \sum_{i=1}^{\lfloor \frac{l_2+r_2}{2} \rfloor} \left( X_{r_2-i+1} - X_{i} \right) ,\\ w(l_1,r_2) + w(l_2,r_1) = \sum_{i=1}^{\lfloor \frac{l_1+r_2}{2} \rfloor} \left( X_{r_2-i+1} - X_{i} \right) + \sum_{i=1}^{\lfloor \frac{l_2+r_1}{2} \rfloor} \left( X_{r_1-i+1} - X_{i} \right) ,\\ \]

对比这两个式子,发现加的项和减的项数量都分别相同,观察项数的分配,发现,在第二个式子中,加的项更集中于靠近 \(r_2\) ,减的项更集中于 \(l_1\) ,所以符合四边形不等式。

然后 ,根据套路 \(g_{i-1,j} \le g_{i,j} \le g_{i,j+1}\) ,倒序跑 DP 即可,时间复杂度 \(O(VP)\) 。
其中 \(g_{i,j}\) 表示 \(f_{i,j}\) 的最小最优决策点。

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
const int N=3010;
const int M=310;
int f[N][M],n,m,w[N],g[N][N],fr[N][M];
bool cmp(int a,int b){return a<b;}
int main(){
	scanf("%d%d",&n,&m);
	fo(i,1,n)scanf("%d",&w[i]);
	sort(w+1,w+n+1,cmp);
	fo(i,1,n){
		fo(j,i+1,n)
			g[i][j]=g[i][j-1] + w[j] - w[(i+j)/2];
	}
	memset(f,127,sizeof(f));
	f[0][0]=0;
	fo(j,1,m){
		fr[n+1][j]=n;
		fd(i,n,1){
			fo(r,fr[i][j-1],fr[i+1][j]){
				int tmp=f[r][j-1] + g[r+1][i];
				if(tmp<f[i][j]){
					f[i][j]=tmp;
					fr[i][j]=r;
				}
			}
		}
	}
	printf("%d\n",f[n][m]);
	
	return 0;
}
上一篇:Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine)) D2. Up the Strip (数学,DP)


下一篇:【数学】乘法逆元