CF1209E Rotate Columns

03 October 2019 | duanyll | Tags: OI 题解 DP

这是一道最近 Codeforces 比赛的题目, 当时在场上昏昏欲睡, 连小的点都没有想出来, 现在再看一下.

题意

给你一个$n \times m$的矩阵, 可以对每一列的元素循环移位, 求每一行的最大值之和的最大值. $(1 \leq n \leq 12, 1 \leq m \leq 2000)$.

分析

$n \leq 12$明示状压. 考虑定义状态$dp[i][s]$表示考虑前$i$列, 其中$s$包括的行已经取了最大值的答案, 那么每次就可以枚举$s$的子集来转移, 复杂度$O(tm3^n)$, 可以水过小数据.

观察分析发现, 答案至少取到每列按照最大值排序的前$n$个值, 因此枚举状压的部分可以降到$O(n3^n)$, 加上按最大值取前$n$列复杂度是$O(t(n3^n+mn\log m))$, 大数据可过.

代码

可以用以下方法取$s$的子集(每次去掉最后一个二进制1):

for (int k = s; ; k = (k - 1) & s) {
    ...
    if (k == 0) break;
}

用以下方法取$s$的超集:

for (int k = s; k < (1 << n); k = (k + 1) | s) {
    ...
}

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

typedef long long int64;

const int INF = 0x3f3f3f3f;
const int MAXN = 14;
const int MAXS = (1 << 12) + 10;
const int MAXM = 2010;

int a[MAXN][MAXM];
int mxval[MAXM];
int dp[MAXN][MAXS];
int col[MAXM];

#include <cctype>
#include <cstdio>

template <typename T = int>
inline T read() {
    T X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch))
    {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) {
        X = (X << 3) + (X << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -X : X;
}

int val[MAXS];  // 预处理每次循环移位的结果

int main() {
    int tcnt = read();
    for (int T = 1; T <= tcnt; T++) {
        int n = read();
        int m = read();
        memset(a, 0, sizeof a);
        memset(col, 0, sizeof col);
        memset(mxval, 0, sizeof mxval);
        memset(dp, 0, sizeof dp);
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= m; j++) {
                a[i][j] = read();
                mxval[j] = max(mxval[j], a[i][j]);
            }
        }
        for (int i = 1; i <= m; i++) {
            col[i] = i;
        }
        sort(col + 1, col + m + 1, [](const int& a, const int& b) -> bool {
            return mxval[a] > mxval[b];
        });
        for (int i = 1; i <= min(n, m); i++) {
            memset(val, 0, sizeof val);
            for (int s = 0; s < (1 << n); s++) {
                for (int j = 0; j < n; j++) {   // 暴力循环移位
                    int now = 0;
                    for (int k = 0; k < n; k++) {
                        if (s & (1 << k)) {
                            now += a[(j + k) % n][col[i]];
                        }
                    }
                    val[s] = max(val[s], now);
                }
            }
            memset(dp[i], 0, sizeof dp[i]);
            for (int s = 0; s < (1 << n); s++) {
                for (int k = s; ; k = (k - 1) & s) {
                    dp[i][s] = max(dp[i][s], dp[i - 1][k] + val[s ^ k]);
                    // clog << dp[i][s] << ' ';
                    if (k == 0) break; // 至少执行一次
                }
            }
            // clog << endl;
        }
        cout << dp[min(n, m)][(1 << n) - 1] << endl;
    }
}