完全背包變種：WHUgirls 矩形布料切割最大化收益 DP 解法

題目模型

原始布料 X×Y，可切割成 N 種小矩形 `xi×yi` 售價 `ci`。切割只能水平或垂直一分為二，可重複切割同種小矩形。求最大收益。
本質：**二維完全背包** + **切割遞歸**。

DP 狀態

`dp[w][h]`：寬 w 高 h 的布料最大收益。
初始 `dp[w][h] = 0` (不切割)。

轉移

1. 直接出售：若存在完全匹配的小矩形 `(w,h)`，`dp[w][h] = max(dp[w][h], c)`。
2. 水平切割：`for k=1..h-1: dp[w][h] = max(dp[w][h], dp[w][k] + dp[w][h-k])`
3. 垂直切割：`for k=1..w-1: dp[w][h] = max(dp[w][h], dp[k][h] + dp[w-k][h])`

計算順序

雙層循環 `w=1..X, h=1..Y`，內層枚舉切割點。復雜度 O(X*Y*(X+Y))，X,Y≤1000 略大，需優化（如僅枚舉有切割意義的 k、或用一維滾動）。

參考題解

u013480600 詳細 DP 分析與代碼