codeforces 1209E1 Rotate Columns (easy version)

题目传送门：codeforcces ， luogu

思路

贪心，暴力搜索

贪心

对于所有列，只有列中最大值在所有列的最大值中前 \(n\) 大才可能对答案有贡献。
证明：若有非前 \(n\) 大的列对某行最大值产生了贡献，则用没有被取的前 \(n\) 大的列代替该行一定更优。所以只有列中最大值在所有列的最大值中前 \(n\) 大才可能对答案有贡献。

暴力搜索

将所有列按列的最大值从大到小排序。根据贪心，答案一定由前 \(n\) 列产生，而 \(n \leq 4\) ，所以直接爆搜就行了。

细节

更新的时候要先保存，不然回溯会出错。

代码

单次时间复杂度\(O(n^{2 \times n - 2})\)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 6, M = 105;

#define LF(i, __l, __r) for (int i = __l; i <= __r; i++)
#define RF(i, __r, __l) for (int i = __r; i >= __l; i--)

struct col { int a[N], mx; } a[M];
int t, n, m, ans, mx[N];
int back[N][N][N];

bool cmp(col a, col b) { return a.mx > b.mx; }

void Init() {
    ans = 0;
    memset(mx, 0, sizeof(mx));
    memset(back, 0, sizeof(back));
    memset(a, 0, sizeof(a));
}

void dfs(int u) {
    if (u == n + 2) {
        int res = 0;
        LF(i, 1, n) res += mx[i];
        ans = max(ans, res);
        return;
    }

    LF(i, 0, n - 1) {
        LF(j, 1, n) {
            int s = i + j;
            if (s > n) s %= n;
            back[u][i][s] = mx[s];
            mx[s] = max(mx[s], a[u].a[j]);
        }
        dfs(u + 1);
        LF(j, 1, n) mx[j] = back[u][i][j];
    }
}

int main() {
    scanf("%d", &t);

    while (t--) {
        Init();
        scanf("%d%d", &n, &m);
        LF(i, 1, n) LF(j, 1, m) {
            scanf("%d", &a[j].a[i]);
            a[j].mx = max(a[j].mx, a[j].a[i]);
        }

        sort(a + 1, a + m + 1, cmp);
        
        dfs(1);
        printf("%d\n", ans);
    }
    return 0;
}