题解 | 取数游戏

这道题非常爽魔，我一个一点没有接触过状压dp的蒟蒻，在DFS题单里刷到了它，花了两个多小时理解题解的每一行代码，代码的结构实在是太全新了！让我受益匪浅

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// 每个格子，要么选，要么不选，那么对于这个N*M矩阵，产生的状态数组合就有2^(n*m)
// 可以达到2^36这么多，显然时间复杂度直接爆炸了，为此我们必须得进行状态压缩
// 于是就能想到使用状态dp算法
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<vector<long long>> a(n, vector<long long>(m));
        for (int i = 0; i < n; i++) { // 得到整个矩阵
            for (int j = 0; j < m; j++) {
                cin >> a[i][j];
            }
        }

        // 接下来对整个矩阵进行状态压缩将状态压缩到一行里，合法的不相邻选择列组合是什么
        vector<long long> state;
        for (int i = 0; i < (1<<m) ; i++) { // m列，则有2^n的列组合，如001,101,111
            if ((i & i << 1) == 0) { 
            // 101 和 010，相当于让001组合相邻元素进行比较，看看是否满足相邻元素不为1
                state.push_back(i); // 将这一101组合压入state，表示一个合法的列组合
            }
        }

        // 得到行内部的合法列组合，接下来就把每一行的和合法列方案选取到的矩阵元素相加，
        // 得到在当前行，不同组合010,101他们的行权值和是多少
        long long s = state.size();
        vector<vector<long long>> rol_sum(n, vector<long long>(s)); 
        // 利用rol_sum记录不同方案下这一行的对应权值和
        for (int i = 0; i < n; i++) { // 每一行
            for (int z = 0; z < s; z++) { // 每一种列方案
                for (int j = 0; j < m; j++) { // 该行上某列的元素值
                    if (state[z] & 1 << j) { 
                        rol_sum[i][z] += a[i][j]; // 第i行第z个方案的列权值和
                    }
                }
            }
        }

        // 之后我们要确定行间也要合法，只需比较上一行和本行，不用管下一行，
        // 因为dp算法只看当前的和上一个的
        vector<vector<long long>> ok(s, vector<long long>(s, 0));
        // 创建一个ok数组，记录第i个合法列组合方案和第j个合法列组合方案是否兼容
        for (int curr = 0; curr < s; curr++) {
            for (int pre = 0; pre < s; pre++) {
                if ((state[curr] & state[pre]) == 0 && (state[curr] & state[pre] << 1) == 0 && (state[curr] & state[pre] >> 1) == 0) {
                    ok[curr][pre] = 1; // 1表示上行的列组合和本行的列组合兼容
                }
            }
        }

        long long DEG = -2e18;
        vector<vector<long long>> dp(n, vector<long long>(s, DEG));
        // 因为要找最大数字和，那我得让dp被初始化为极其小的数，然后dp表示在第i行，当使用第k个列组合方案时，以该行为结尾的矩阵能取得的最大合法数字和
        for (int i = 0; i < s; i++) {
            dp[0][i] = rol_sum[0][i]; // 第0行的dp当然是取第0行的行权值和
        }
        for (int i = 1; i < n; i++) {
            for (int curr = 0; curr < s; curr++) {
                for (int pre = 0; pre < s; pre++) {
                    if (ok[curr][pre]) {
                        dp[i][curr] = max(dp[i][curr], dp[i-1][pre] + rol_sum[i][curr]);
                    }
                    
                }
            }
        }
        long long maxx = DEG;
        for (int i = 0; i < s; i++) {
            maxx = max(maxx, dp[n-1][i]); // dp[n-1]表示以最后一行为结尾的矩阵所能选出的最大权值和，[i]则是第i个列组合方案下的最大权值和
        }
        cout << maxx << '\n';
        
        
    }
    return 0;
}