HDU 1565 方格取數 - 狀態壓縮 DP 求最大權獨立集

問題描述

N×N 棋盤 (N ≤ 20)，每格有非負權值。選取若干格子，任兩格不相鄰 (無公共邊)，最大化權值和。多測試案例。

狀態壓縮 DP

逐行處理。每行狀態用 N 位二進制數表示：第 j 位 = 1 表示選中第 j 列。合法狀態：無相鄰 1 (即 (state & (state << 1)) == 0)。相鄰行狀態不衝突：無同列同為 1 (即 (state_i & state_{i-1}) == 0)。

DP 定義

dp[row][state] = 前 row 行，第 row 行狀態為 state 的最大權值和。

轉移

for row = 1..N:
    for each valid state cur:
        val = sum of board[row][col] where cur has bit col
        for each valid state prev:
            if (cur & prev) == 0:
                dp[row][cur] = max(dp[row][cur], dp[row-1][prev] + val)

答案

max_{state} dp[N][state]。

預處理優化

• 預計算所有合法狀態列表 valid_states[] (最多 Fib(N+2) 個，N=20 時 17711)。
• 預計算每狀態的權值和 row_val[row][state]。
• 預計算兼容列表 compat[state] = {prev | (prev & state) == 0}。

參考代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 22;
const int MAXS = 18005; // 上界 Fib(22) = 17711

int dp[MAXN][MAXS];
int board[MAXN][MAXN];
int valid[MAXS], val[MAXN][MAXS];
vector compat[MAXS];
int N, S;

bool is_valid(int state) {
    return (state & (state << 1)) == 0;
}

int main() {
    while (scanf("%d", &N) == 1) {
        for (int i = 1; i <= N; i++)
            for (int j = 0; j < N; j++)
                scanf("%d", &board[i][j]);

        // 生成合法狀態
        S = 0;
        for (int s = 0; s < (1<

複雜度

  
狀態數 S ≈ 1.7萬 (N=20)。
  
兼容檢查 O(S²) 預計算 ≈ 3億，略大但可接受 (C++ 優化後 ~0.5s)。可用「按位枚舉子集」優化至 O(S·2^{N/2})，但非必要。
  
DP 主循環 O(N·S·avg_compat) ≈ 20·1.7萬·5000 ≈ 1.7億，配合優化可通過。
  
空間 O(N·S) ≈ 36萬 int，極小。


狀壓 DP 模板總結

  
定義狀態 (二進制位)。
  
篩選合法狀態 (行內約束)。
  
預計算行權值、行間兼容。
  
逐行 DP 轉移。
  
取最後一行最大值。