题解 | #取数游戏#

题目链接

取数游戏

题目描述

给定一个 $R \cdot C$ 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻的8个格子中的一个，即认为这两个数字相邻），求取出数字和的最大值。

解题思路

这是一个在网格中选取不相邻元素以获取最大和的经典问题。由于矩阵的维度非常小（ $R, C \le 6$ ），这提示我们可以使用状态压缩动态规划（Bitmask DP）来解决。

1. 核心思想与状态定义

我们逐行处理矩阵，计算每一行在不同选取方案下的最大和。

我们定义一个二维DP数组： $dp[i][mask]$ 。

$i$ ：代表当前处理到第 $i$ 行（从0开始）。
$mask$ ：一个整数，它的二进制表示法代表了第 $i$ 行的选取状态。如果 $mask$ 的第 $j$ 位是 $1$ ，表示我们选取了第 $i$ 行第 $j$ 列的数字；如果是 $0$ ，则不选取。
$dp[i][mask]$ 的值：表示处理完前 $i+1$ 行（即第0到i行），并且第 $i$ 行的选取状态恰好为 $mask$ 时，所能获得的最大数字和。

2. 状态转移

为了计算 $dp[i][mask_i]$ ，我们需要考虑它能从上一行（第 $i-1$ 行）的哪些状态转移而来。

$dp[i][mask_i] = \mathit{current\_row\_sum} + \max(dp[i-1][mask_{i-1}])$

这里的 $\mathit{current\_row\_sum}$ 是第 $i$ 行按照 $mask_i$ 状态选取的数字之和。

$max$ 操作则需要遍历上一行所有可能的选取状态 $mask_{i-1}$ ，但前提是 $mask_i$ 和 $mask_{i-1}$ 必须是兼容的。

3. 兼容性判断

兼容性包含两个层面：

A. 行内兼容性

一个 $mask$ 本身必须是合法的。根据题意，同一行内不能选取相邻的数字。

这意味着 $mask$ 的二进制表示中，不能有两个相邻的 $1$ 。

用位运算可以高效地检查： $(mask \ \& \ (mask \ll 1)) == 0$ 。

B. 行间兼容性

第 $i$ 行的状态 $mask_i$ 必须与第 $i-1$ 行的状态 $mask_{i-1}$ 兼容。

如果我们在第 $i$ 行选取了第 $j$ 列的数字（即 $mask_i$ 的第 $j$ 位为1），那么在第 $i-1$ 行，第 $j-1$ , $j$ , $j+1$ 列的数字都不能被选取。

这可以用三个位运算条件来概括：

$(mask_i \ \& \ mask_{i-1}) == 0$ （正上方不相邻）
$(mask_i \ \& \ (mask_{i-1} \ll 1)) == 0$ （左上方不相邻）
$(mask_i \ \& \ (mask_{i-1} \gg 1)) == 0$ （右上方不相邻）

只有同时满足这两个层面兼容性的 $mask_i$ 和 $mask_{i-1}$ 才能进行状态转移。

4. 算法流程

初始化 (Base Case)：处理第 $0$ 行。对于所有满足行内兼容性的 $mask$ ，直接计算 $dp[0][mask] = sum$ ，其中 $sum$ 是第 $0$ 行按 $mask$ 选取数字的和。
递推：从第 $1$ 行开始，遍历到第 $R-1$ 行：对于每个 $i$ 从 $1$ 到 $R-1$ ：对于每个满足行内兼容性的 $mask_i$ ： $max\_prev\_sum = 0$ 对于每个满足行内兼容性的 $mask_{i-1}$ ：如果 $mask_i$ 和 $mask_{i-1}$ 满足行间兼容性： $max\_prev\_sum = \max(max\_prev\_sum, dp[i-1][mask_{i-1}])$ $dp[i][mask_i] = \text{sum}(i, mask_i) + max\_prev\_sum$
最终答案：遍历 $DP$ 表的最后一行，即 $dp[R-1]$ ，其中的最大值就是最终答案。不要忘记，如果不选取任何数，和为0，所以最终答案至少为0。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int R, C;
    cin >> R >> C;
    vector<vector<int>> grid(R, vector<int>(C));
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            cin >> grid[i][j];
        }
    }

    int max_mask = 1 << C;
    vector<vector<int>> dp(R, vector<int>(max_mask, 0));

    // Base case: 第 0 行
    for (int mask = 0; mask < max_mask; ++mask) {
        if ((mask & (mask << 1)) == 0) { // 行内兼容
            int current_sum = 0;
            for (int j = 0; j < C; ++j) {
                if ((mask >> j) & 1) {
                    current_sum += grid[0][j];
                }
            }
            dp[0][mask] = current_sum;
        }
    }

    // DP 递推
    for (int i = 1; i < R; ++i) {
        for (int mask_i = 0; mask_i < max_mask; ++mask_i) {
            if ((mask_i & (mask_i << 1)) == 0) { // 当前行 mask_i 必须合法
                int current_sum = 0;
                for (int j = 0; j < C; ++j) {
                    if ((mask_i >> j) & 1) {
                        current_sum += grid[i][j];
                    }
                }

                int max_prev_sum = 0;
                for (int mask_prev = 0; mask_prev < max_mask; ++mask_prev) {
                    // 检查行间兼容性
                    if ((mask_i & mask_prev) == 0 &&
                        (mask_i & (mask_prev << 1)) == 0 &&
                        (mask_i & (mask_prev >> 1)) == 0) {
                        max_prev_sum = max(max_prev_sum, dp[i-1][mask_prev]);
                    }
                }
                dp[i][mask_i] = current_sum + max_prev_sum;
            }
        }
    }

    int ans = 0;
    for (int mask = 0; mask < max_mask; ++mask) {
        ans = max(ans, dp[R - 1][mask]);
    }
    cout << ans << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            solve(sc);
        }
    }

    private static void solve(Scanner sc) {
        int R = sc.nextInt();
        int C = sc.nextInt();
        int[][] grid = new int[R][C];
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                grid[i][j] = sc.nextInt();
            }
        }

        int maxMask = 1 << C;
        int[][] dp = new int[R][maxMask];

        // Base case: 第 0 行
        for (int mask = 0; mask < maxMask; mask++) {
            if ((mask & (mask << 1)) == 0) { // 行内兼容
                int currentSum = 0;
                for (int j = 0; j < C; j++) {
                    if (((mask >> j) & 1) == 1) {
                        currentSum += grid[0][j];
                    }
                }
                dp[0][mask] = currentSum;
            }
        }

        // DP 递推
        for (int i = 1; i < R; i++) {
            for (int maskI = 0; maskI < maxMask; maskI++) {
                if ((maskI & (maskI << 1)) == 0) { // 当前行 maskI 必须合法
                    int currentSum = 0;
                    for (int j = 0; j < C; j++) {
                        if (((maskI >> j) & 1) == 1) {
                            currentSum += grid[i][j];
                        }
                    }

                    int maxPrevSum = 0;
                    for (int maskPrev = 0; maskPrev < maxMask; maskPrev++) {
                        // 检查行间兼容性
                        if ((maskI & maskPrev) == 0 &&
                            (maskI & (maskPrev << 1)) == 0 &&
                            (maskI & (maskPrev >> 1)) == 0) {
                            maxPrevSum = Math.max(maxPrevSum, dp[i - 1][maskPrev]);
                        }
                    }
                    dp[i][maskI] = currentSum + maxPrevSum;
                }
            }
        }

        int ans = 0;
        for (int mask = 0; mask < maxMask; mask++) {
            ans = Math.max(ans, dp[R - 1][mask]);
        }
        System.out.println(ans);
    }
}

def solve():
    R, C = map(int, input().split())
    grid = []
    for _ in range(R):
        grid.append(list(map(int, input().split())))

    max_mask = 1 << C
    dp = [[0] * max_mask for _ in range(R)]

    # Base case: 第 0 行
    for mask in range(max_mask):
        if (mask & (mask << 1)) == 0:  # 行内兼容
            current_sum = 0
            for j in range(C):
                if (mask >> j) & 1:
                    current_sum += grid[0][j]
            dp[0][mask] = current_sum

    # DP 递推
    for i in range(1, R):
        for mask_i in range(max_mask):
            if (mask_i & (mask_i << 1)) == 0:  # 当前行 mask_i 必须合法
                current_sum = 0
                for j in range(C):
                    if (mask_i >> j) & 1:
                        current_sum += grid[i][j]

                max_prev_sum = 0
                for mask_prev in range(max_mask):
                    # 检查行间兼容性
                    if (mask_i & mask_prev) == 0 and \
                       (mask_i & (mask_prev << 1)) == 0 and \
                       (mask_i & (mask_prev >> 1)) == 0:
                        max_prev_sum = max(max_prev_sum, dp[i-1][mask_prev])
                
                dp[i][mask_i] = current_sum + max_prev_sum
    
    ans = 0
    if R > 0:
        ans = max(dp[R - 1])
    
    print(ans)


T = int(input())
for _ in range(T):
    solve()

算法及复杂度

算法：状态压缩动态规划 (Bitmask DP)
时间复杂度： $\mathcal{O}(R \cdot (2^C)^2)$ 。 $DP$ 状态共有 $R \cdot 2^C$ 个。计算每个状态需要遍历上一行的所有 $2^C$ 个状态。因此总复杂度为 $R \cdot 2^C \cdot 2^C = R \cdot 4^C$ 。由于 $R,C \le 6$ ，这是完全可以接受的。
空间复杂度： $\mathcal{O}(R \cdot 2^C)$ 。用于存储 $DP$ 表。可以优化到 $\mathcal{O}(2^C)$ ，因为计算第 $i$ 行的状态只需要第 $i-1$ 行的信息。