BZOJ 1190 [HNOI2007] 夢幻島寶珠：分層 01 背包 DP

題目大意

01 背包問題。物品重量 w ≤ 2^30，但每個 w 可分解為 a × 2^b (a ≤ 10, b ≤ 30)。背包容量 W ≤ 2^30。求最大價值。

核心思想：按 2 的冪次分層 DP

將物品按指數 b 分為 31 層 (0~30)。第 b 層物品重量形如 a×2^b (a≤10)。

定義 `f[b][j]`：在考慮前 b 層（即低 b 位）物品時，剩餘容量為 `j×2^b + (W & (2^b-1))` 的最大價值。j ≤ 1000 足夠（因 a≤10，總重量低位貢獻有限）。

DP 流程

1. 層內 01 背包： 對每層物品，按標準 01 背包更新 `f[b][j]` (j 從大到小)。
2. 層前綴最大值： `f[b][j] = max(f[b][j], f[b][j-1])`，表示容量≥j×2^b 時的最大值。
3. 層間轉移（高位向低位）： 從 b=1 到 30：

   for (int j = min(1000, W>>b); j >= 0; j--)
          for (int k = 0; k <= j; k++)
              f[b][j] = max(f[b][j], f[b][j-k] + f[b-1][min(k*2 + ((W>>(b-1))&1), 1000)]);

   含義：在第 b 層花費 k×2^b 容量，剩餘 (j-k)×2^b 留給低層；低層可用容量折算為第 b-1 層的單位數為 `k*2 + 當前位`。
4. 答案為所有 `f[b][j]` 中最大值。

關鍵點解析

• 狀態壓縮利用了權重的特殊結構（低位權重小，高位權重大且為 2 的冪次倍數）。
• j 限制在 1000 是因為 Σa_i ≤ 1000（n≤100, a≤10），高位不可能消耗過多單位。
• 轉移方程巧妙處理了進位：`k*2` 來自 2^b = 2×2^{b-1}，`((W>>(b-1))&1)` 來自背包容量 W 的第 b-1 位。