2018 Multi-University Training Contest 10 CSGO（HDU - 6435）（最远曼哈顿距离）

有 n 种主武器，m 种副武器。每种武器有一个基础分数k种属性值 X[i] 。

选出一种主武器 mw 和一种副武器 sw，使得两种武器的分数和 + 每个属性的差值尽量大。（参考下面的式子）

多维的最远曼哈顿距离。

因为对于每一种属性对答案的贡献，要么是 Xmw[i] - Xsw[i] ，要么是 Xsw[i] - Xmv[i]。

枚举每个主武器所有属性的符号，副武器的符号与主武器相反。

然后每次从主武器和副武器里面分别找一个属性值和基础分数的总和最大的，用这两个最大值的和更新答案。

因为k <= 5，所以枚举所有符号的复杂度是 2^k <= 32，总复杂度是 O(2^k * nk)。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn =  + ;

const LL INF = 1e19/;

int n, m, k, t;

LL a[maxn][], b[maxn][];

LL sum;

int main()

{

    scanf("%d", &t);

    for (int ca = ; ca <= t; ca++)

    {

        LL ans = ;

        scanf("%d%d%d", &n, &m, &k);

        for (int i = ; i <= n; i++)

        for (int j = ; j <= k; j++) scanf("%lld", &a[i][j]);

        for (int i = ; i <= m; i++)

        for (int j = ; j <= k; j++) scanf("%lld", &b[i][j]);

        for (int s = ; s <= (<<k)-; s++)

        {

            LL max1 = -INF, max2 = -INF;

            for (int i = ; i <= n; i++)

            {

                sum = a[i][];

                for (int j = ; j <= k; j++)

                    sum += a[i][j]*(s>>(j-) &  ? :-);

                max1 = max(max1, sum);

            }

            for (int i = ; i <= m; i++)

            {

                sum = b[i][];

                for (int j = ; j <= k; j++)

                    sum += b[i][j]*(s>>(j-) &  ? -:);

                max2 = max(max2, sum);

            }

            ans = max(ans, max1+max2);

        }

        printf("%lld\n", ans);

    }

}