题目描述

难度分:$1331$

输入$n(1 \leq n \leq 1000)$，$m(0 \leq m \leq n)$和一个$n$行$3$列的矩阵$a$，矩阵中的元素处于值域$[-10^{10},10^{10}]$。

从$n$行中选择$m$行，输出“$|$第一列元素和$|+|$第二列元素和$|+|$第三列元素和$|$”的最大值。

输入样例$1$

5 3
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9

输出样例$1$

56

输入样例$2$

5 3
1 -2 3
-4 5 -6
7 -8 -9
-10 11 -12
13 -14 15

输出样例$2$

54

输入样例$3$

10 5
10 -80 21
23 8 38
-94 28 11
-26 -2 18
-69 72 79
-26 -86 -54
-72 -50 59
21 65 -32
40 -94 87
-62 18 82

输出样例$3$

638

输入样例$4$

3 2
2000000000 -9000000000 4000000000
7000000000 -5000000000 3000000000
6000000000 -1000000000 8000000000

输出样例$4$

30000000000

算法

枚举+贪心

假设矩阵的三列分别为$a$、$b$、$c$。这题比较烦的就是绝对值，我们要想办法把绝对值去掉。如果第一列元素和$\geq 0$，第二列元素和$\lt 0$，第三列元素和$\geq 0$。

去掉绝对值，要计算的式子就是：第一列元素和$-$第二列元素和$+$第三列元素和$=\Sigma_{i=1}^{m}(a[t_i]-b[t_i]+c[t_i])$，$t_1,t_2,…,t_m$是选出来的行号。

要让答案尽量大，按照$a[i]-b[i]+c[i]$从大到小排序，计算前$m$ 项的“$|$第一列元素和$|+|$第二列元素和$|+|$第三列元素和$|$。

因此，我们枚举$2^3=8$种元素和的正负号组合，这样可以把绝对值拆开，每种情况算一个最优解出来，这些解的最大值就是最终答案。

复杂度分析

时间复杂度

列状态一共有$2^3=8$种，对于每种状态的求解，瓶颈在于排序的$O(nlog_2n)$。因此，整个算法的时间复杂度为$O(2^mnlog_2n)$，$m$为列数，本题中$m=3$。

空间复杂度

对于每种状态，需要在给定符号的情况下对$sign_a \times a[i]+sign_b \times b[i]+sign_c \times c[i]$排序（$sign_a$、$sign_b$、$sign_c$分别为第一列到第三列的符号），因此就要线性空间存$n$个元素。所以算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 1010;
int n, m;

struct Tuple {
    LL a, b, c;
} tup[N];

LL solve(int mask) {
    vector<LL> sign;
    for(int i = 0; i < 3; i++) {
        if(mask>>i&1) {
            sign.push_back(1);
        }else {
            sign.push_back(-1);
        }
    }
    vector<pair<LL, int>> arr;
    for(int i = 1; i <= n; i++) {
        arr.push_back({sign[0]*tup[i].a + sign[1]*tup[i].b + sign[2]*tup[i].c, i});
    }
    sort(arr.begin(), arr.end());
    LL a = 0, b = 0, c = 0;
    for(int i = n - m; i < n; i++) {
        a += tup[arr[i].second].a;
        b += tup[arr[i].second].b;
        c += tup[arr[i].second].c;
    }
    return abs(a) + abs(b) + abs(c);
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%lld%lld%lld", &tup[i].a, &tup[i].b, &tup[i].c);
    }
    if(m == 0) {
        puts("0");
        return 0;
    }
    LL ans = -1e18;
    for(int mask = 0; mask < 8; mask++) {
        ans = max(ans, solve(mask));
    }
    printf("%lld\n", ans);
    return 0;
}