HDU 3127：完全背包變形——二維費用與旋轉優化

題目大意

有 n 種磚塊，每種有長 aᵢ、寬 bᵢ、價值 cᵢ。給定大矩形 X × Y，磚塊可旋轉 90°，無限供應。求填滿大矩形的最大價值（允許不完全填滿，但磚塊不得重疊超出邊界）。

動態規劃模型

dp[i][j] 表示 i × j 矩形的最大價值。
轉移：枚舉每種磚塊的兩種方向（原向與旋轉），若 a ≤ i 且 b ≤ j，可將磚塊放在左上角，剩餘區域分為右側 (i-a) × j 和下方 a × (j-b) 兩個子矩形（或對稱分割）。取最大值。
dp[i][j] = max(dp[i][j], dp[i-a][j] + dp[a][j-b] + c) 及 dp[i][j-b] + dp[i-a][b] + c。

代碼實現

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

int F[1009][1009], w[10][3];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, X, Y; scanf("%d%d%d", &n, &X, &Y);
        for (int i = 0; i < n; ++i) scanf("%d%d%d", &w[i][0], &w[i][1], &w[i][2]);
        memset(F, 0, sizeof(F));
        for (int i = 0; i <= X; ++i)
            for (int j = 0; j <= Y; ++j)
                for (int k = 0; k < n; ++k) {
                    // 原向
                    if (w[k][0] <= i && w[k][1] <= j) {
                        F[i][j] = max(F[i][j], F[i-w[k][0]][j] + F[w[k][0]][j-w[k][1]] + w[k][2]);
                        F[i][j] = max(F[i][j], F[i][j-w[k][1]] + F[i-w[k][0]][w[k][1]] + w[k][2]);
                    }
                    // 旋轉 90°
                    swap(w[k][0], w[k][1]);
                    if (w[k][0] <= i && w[k][1] <= j) {
                        F[i][j] = max(F[i][j], F[i-w[k][0]][j] + F[w[k][0]][j-w[k][1]] + w[k][2]);
                        F[i][j] = max(F[i][j], F[i][j-w[k][1]] + F[i-w[k][0]][w[k][1]] + w[k][2]);
                    }
                    swap(w[k][0], w[k][1]); // 恢復
                }
        printf("%d\n", F[X][Y]);
    }
    return 0;
}

關鍵點解析

• 二維完全背包：外層循環 i, j 遞增，保證子狀態已計算。
• 磚塊放置後剩餘區域有兩種分割方式（右+下、下+右），需同時考慮。
• 旋轉處理：swap(a, b) 後再次嘗試，再 swap 回原狀。
• 複雜度：O(X × Y × n)，X, Y ≤ 1000，n ≤ 10，約 10⁷ 操作，可接受。

狀態轉移圖示

+-----------+     放置 a×b 磚塊
| a × b     |     剩餘分割：
+-----------+----------+
|           |          |
|  (i-a)×j  |  a×(j-b) |   或對稱分割
|           |          |
+-----------+----------+

此題展示了如何將幾何填充問題轉化為二維 DP，並處理旋轉與多種分割策略。