网站首页
编程语言
数据库
系统相关
其他分享
编程问答
P6246
2024-09-10
[IOI2000] 邮局 P10967/P4767/P6246
P10967设在\(1\simi\)装了\(j\)个邮局的答案\(f_{i,j}\):\(f_{i,j}=\min\{f_{k,j-1}+w_{k+1,i}\}\),其中\(w_{l,r}\)为\(l\simr\)有一个邮局的最小距离。\(w_{l,r}\)怎么求?在中位点装邮局。那么有\(w_{l,r}=w_{l,r-1}+x_j-x_{[(i+j)/2]}\)。其中\(x\)是村庄位置。