【HDU】6435 CSGO 求K维曼哈顿距离下距离最大点对

题目大意

给定 $n$ 种主武器和 $m$ 种副武器，每种武器都有一个攻击力 $a_i$。选择一种主武器和一种副武器，使得

$$S_m + S_s + \sum |a_m[i] - a_s[i]|$$

最大化。

题目链接

思路

$\sum |a_m[i] - a_s[i]|$ 类似于曼哈顿距离 $|x_1 - x_2| + |y_1 - y_2|$ 的形式。

如果我们把曼哈顿距离同属性的放到一块，再去掉绝对值，就会变成形如 $(-x_1 + y_1) + (x_1 - y_1)$，二维的话就有 $4$ 种情况，$k$ 维的话就有 $2^k$ 种形式。

我们单独把每个武器的副属性给展开成这 $2^k$ 种形式，用二进制 $01$ 表示每个属性是 $+$ 还是 $-$，把它们全部相加，并且把攻击力加上，记为 $S_m[i][j]$，其中 $i$ 为第 $i$ 把主武器，$j$ 为展开形式编号。

$k’$ 就是 $k$ 按位取反（对应到每个属性就是正负相反）。

那么

$$\max\left(S_m + S_s + \sum |a_m[i] - a_s[i]|\right) = \max(S_m[i][k] + S_s[j][k']),\quad i \in [1,n],\ j \in [1,m]$$

然而，遍历这个式子的时间复杂度是 $O(nmk)$，所以我们想办法化简这个式子。

考虑一个简单的问题：有 $a_n, b_m$，求 $\max(a[i] + b[j]),\ i \in [1,n],\ j \in [1,m]$。直接硬算需要两重循环。

注意到 $a[i] + b[j]$ 这个组合遍历到了所有 $a[i], b[j]$ 的组合，即任意指定的 $i, j$，$a[i], b[j]$ 都会被遍历到。

$\max(a[i] + b[j]) \le \max(a[i]) + \max(b[j])$，而 $\max(a[i]) + \max(b[j])$ 这个值也一定能被遍历到，所以就有

$$\max(a[i] + b[j]) = \max(a[i]) + \max(b[j])$$

那么这么算就从两重循环变成了两个循环。

对应到这个题目中（合法的 $k, k’$ 组合必然比不合法的组合大，比如 $+5, -2$ 就比 $-5, +2$ 要大），上面式子也可以继续化简：

$$\max(S_m[i][k] + S_s[j][k']) = \max(S_m[i][k]) + \max(S_s[j][k'])$$

而对于每个 $k$，我们只需要得到它的最大值，所以 $i$ 这一维也可以省去，令 $S_m[k] = \max_i(S_m[i][k])$。那么上式子可以再度化简为：

$$\max(S_m[k] + S_s[k'])$$

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int T, n, m, k, s[8], x;

const long long INF = 0x7f7f7f7f;

long long s1[1 <<11], s2[1 << 11];

int main()
{
    scanf("%d", &T);
    while(T--) {
        for(int i = 0; i < 1 << 11; ++i)
            s1[i] = s2[i] = -INF;
        scanf("%d%d%d", &n, &m, &k);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &x);
            for(int j = 1; j <= k; ++j)
                scanf("%d", &s[j]);
            for(int j = 0; j < 1 << k; ++j) {
                long long sum = x;
                for(int l = 1; l <= k; ++l) {
                    if((j >> (l - 1)) & 1)
                        sum += s[l];
                    else
                        sum -= s[l];
                }
                s1[j] = max(s1[j], sum);
            }
        }
        for(int i = 1; i <= m; ++i) {
            scanf("%d", &x);
            for(int j = 1; j <= k; ++j)
                scanf("%d", &s[j]);
            for(int j = 0; j < 1 << k; ++j) {
                long long sum = x;
                for(int l = 1; l <= k; ++l) {
                    if((j >> (l - 1)) & 1)
                        sum -= s[l]; //直接反着存，相当于直接取反了
                    else
                        sum += s[l];
                }
                s2[j] = max(s2[j], sum);
            }
        }
        long long ans = 0;
        for(int i = 0; i <= 1 << k; ++i)
            ans = max(ans, s1[i] + s2[i]);
        printf("%lld\n", ans);
    }
    return 0;
}