HDU 2845 Beans：雙重線性動態規劃解法詳解

題目簡介

在一個 M × N 的矩陣中，每個格子有一顆豆子，豆子具有不同的品質值。你需要選擇一些豆子食用，使總品質值最大。規則如下：若吃掉座標 (x, y) 的豆子，則同行相鄰的 (x, y-1) 和 (x, y+1) 不可吃，且上下兩行（即 x-1 行和 x+1 行）的所有豆子也不可吃。目標是求可獲得的最大品質總和。

題目連結：HDU 2845

解題思路

由於 M × N ≤ 200,000，無法直接用二維 DP，但可以將問題拆解為兩次一維 DP：

1. 行內 DP：對每一行獨立計算在不選相鄰格子的情況下能獲得的最大品質。狀態轉移方程：tmp[j] = max(tmp[j-1], a[i+j-1] + tmp[j-2])，其中 tmp[j] 表示前 j 列的最大值。最終 tmp[m] 即為該行的最大值，存入 row[cnt++]。
2. 行間 DP：因為相鄰兩行不能同時選，對 row[] 數組再做一次 DP：dp[i] = max(dp[i-1], dp[i-2] + row[i])。最終 dp[cnt-1] 即為答案。

代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX = 200000 + 5;
int row[MAX], a[MAX], dp[MAX], tmp[MAX];

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) != EOF) {
        memset(tmp, 0, sizeof(tmp));
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= m * n; i++) scanf("%d", &a[i]);
        int cnt = 1;
        for (int i = 1; i <= m * n; i += m) {
            tmp[1] = a[i];
            for (int j = 2; j <= m; j++) {
                tmp[j] = max(tmp[j-1], a[i+j-1] + tmp[j-2]);
            }
            row[cnt++] = tmp[m];
        }
        dp[1] = row[1];
        for (int i = 2; i < cnt; i++) {
            dp[i] = max(dp[i-1], dp[i-2] + row[i]);
        }
        printf("%d\n", dp[cnt-1]);
    }
    return 0;
}

複雜度分析

時間複雜度 O(M×N)，空間複雜度 O(M×N)，滿足題目限制。