2023-09-21
题目
难度&重要性(1~10):8.5
题目来源
luogu
题目算法
状压 dp,数学
解题思路
这道题我们首先要考虑如何去优化曼哈顿距离。(不然它怎么不玩欧式距离)
首先这是一个普通的曼哈顿距离:\(\sum\limits_{i=1}^d|A_i-B_i|\)
敲重点了,我们可以将 \(|A_i-B_i|\) 化为 \(\max\{A_i-B_i,B_i-A_i\}\)
即 \(\sum\limits_{i=1}^d\max\{A_i-B_i,B_i-A_i\}\)
这样做有什么好处呢?
因为 \(\max\) 是满足分配律的:
\(\max\{a,b\}+\max\{c,d\}=\max\{a+b,a+c,b+c,b+d\}\)
这样曼哈顿距离就表示为:\(\max\limits_{k\in\{1,-1\}}\{\sum\limits_{i=1}^dk\times A_i-\sum\limits_{i=1}^dk\times B_i\}\)
这样我们就只需要得到 \(\max\limits_{i=1,k\in\{1,-1\}}^n\{\sum\limits_{j=1}^dk\times a_{i,j}\}\) 和 \(\min\limits_{i=1,k\in\{1,-1\}}^n\{\sum\limits_{j=1}^dk\times a_{i,j}\}\)。
只需要一减就是答案了。
完成状态
已完成