HDU 2845 Beans：二維 DP 吃豆子遊戲

問題描述

M×N 矩陣，每格有一顆豆子，值為品質值。吃掉 (x, y) 後，不能吃 (x, y-1), (x, y+1)（同行相鄰），也不能吃 x-1 行和 x+1 行的所有豆子。求最大總品質。M×N ≤ 200,000。

降維打擊：行間獨立 → 列間獨立

1. 行內 DP：對於單行，不能吃相鄰格子 → 經典「不相鄰最大和」：
   dp[i][0] 不吃第 i 格，dp[i][1] 吃第 i 格
   dp[i][0] = max(dp[i-1][0], dp[i-1][1])
dp[i][1] = dp[i-1][0] + val[i]
   行最大值 = max(dp[N][0], dp[N][1])
2. 行間 DP：吃了某行就不能吃相鄰行 → 同樣結構！將每行的最大值作為新「格子值」，再跑一遍 1D DP

參考代碼（C++）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 200005;
int dp0[MAXN], dp1[MAXN], val[MAXN], row_max[MAXN];

int solve_row(int *a, int len) {
    dp1[1] = a[1]; dp0[1] = 0;
    for (int i = 2; i <= len; i++) {
        dp1[i] = dp0[i-1] + a[i];
        dp0[i] = max(dp0[i-1], dp1[i-1]);
    }
    return max(dp0[len], dp1[len]);
}

int main() {
    int M, N;
    while (~scanf("%d%d", &M, &N)) {
        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= N; j++) scanf("%d", &val[j]);
            row_max[i] = solve_row(val, N);
        }
        printf("%d\n", solve_row(row_max, M));
    }
    return 0;
}

複雜度分析

• 行內 DP：O(N) 每行，共 M 行 → O(MN)
• 行間 DP：O(M)
• 總時間：O(MN)，MN ≤ 200,000 極快
• 空間：O(max(M,N))

關鍵洞察

1. 約束可分解：同行相鄰互斥、相鄰行整體互斥 → 兩層相同結構
2. 狀態壓縮：只需上一行/格的兩個狀態，空間 O(1) 可優化
3. 同類問題：「打家劫舍 II」「棋盤放國王」等