# 题目描述

给定一个向量，可以对它的各维度取绝对值后求和，得到一个非负整数，我们称之为这个向量的向量价值。

现在，给你 $n$ 个 $m$ 维向量，可以从中任意挑选一组向量，求和得到一个 $m$ 维的和向量，求和向量最大的向量价值。

# 输入格式

第一行两个正整数 $m$，$n$，分别表示输入向量的维度和输入向量的个数；其中 $1 \le m \le 8$，$1 \le n \le 200000$。

接下来 $n$ 行，每行 $m$ 个正整数，表示第 $i$ 个向量的 $m$ 个维度，向量的每个维度 $v_j$ 有 $−2 \times 10^5 \le v_j \le 2 \times 10^5$。

# 输出格式

一个正整数，表示能得到的和向量最大的向量价值。

# 输入样例

3 4

1 2 3

-7 -5 9

4 5 6

1 1 4

# 输出样例

27

# 样例解释

选中第 $1, 3, 4$ 个向量，它们的和向量的向量价值是 $|6| + |8| + |13| = 27$，而且没有其它选择使得得到的和向量的向量价值大于 $27$。

# 题解：枚举 + 状态压缩

看到 $m$ 的数据范围这么小，不难猜到我们应该要枚举这个最大价值的和向量的每一维是正是负。我们可以用一个二进制数来枚举正负情况，对于一个确定的正负情况，我们可以重新定义一个向量的向量价值：如果枚举的这一维是正数，那么这个向量的这一维产生的贡献为其本身；如果这一维是负数，则恰好相反。然后我们将所有贡献大于 $0$ 的向量选出来就是答案了。

看上去没问题，有的人（对就是我）会说：但是你如何保证选完所有贡献大于 $0$ 的向量之后，它们的和向量还能符合我们所假定的正负情况呢？比如当前枚举 “正负正”，我们拿到的向量组是三个 $(-7, -8, 1)$，它们在该正负情况下的贡献为 $2$，加起来为 $6$，但实际上和向量是 $(-21, -24, 3)$，是 “负负正” 呀！一旦出现这种情况，我们定义的权值加起来就不符合实际和向量的价值！别急，接下来给出两个结论，从而保证这个做法的正确性。

1. 最大的那个答案所对应的正负情况在枚举到的时候一定不会出现这种错误情况。这个显然。

2. 即便是枚举到的正负情况和最后我们选完的和向量的实际正负情况不符，在错误情况下定义的权值一定不会超过它在正确情况下所计算得的权值。比如对于三个 $(-7, -8, 1)$，如果我们枚举的是 “负负正”，所得的权值为 $16$，和起来是 $48$，比错误情况下大。这是因为错误情况下我们把某些维度的贡献由正的算成了负的，所以只会更小不会更大。

时间复杂度：$O(2^m nm)$。

参考代码：

#include <stdio.h>

typedef long long ll;

int m, n, sign[10], vec[200010][10];

ll maxVal;

ll max(ll a, ll b)

{

    return (a > b) ? a : b;

}

int main()

{

    // freopen("F.in", "r", stdin);

    // freopen("F.out", "w", stdout);

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

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

        for (int j = 1; j <= m; ++ j)

            scanf("%d", &vec[i][j]);

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

    {

        for (int j = 1; j <= m; ++ j)

            if (i >> (m - j) & 1)

                sign[j] = 1;

            else

                sign[j] = -1;

        ll sum = 0;

        for (int j = 1; j <= n; ++ j)

        {

            ll s = 0;

            for (int k = 1; k <= m; ++ k)

                s += sign[k] * vec[j][k];

            if (s > 0)

                sum += s;

        }

        maxVal = max(maxVal, sum);

    }

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

    return 0;

}