HDU 1069 Monkey and Banana：箱子堆疊最長遞增子序列變體

問題描述

給 n（≤30）種磚塊，每種三維 (x,y,z)。可任意旋轉（任意兩維為底，第三維為高），無限供應。堆疊規則：上層磚塊底面長寬嚴格小於下層對應邊。求最大高度。

轉化為 LIS

1. 每種磚塊產生 3 種朝向（長≥寬規範化），共 3n 種塊，每種無限個 → 但因嚴格遞減，同一朝向最多用一次（否則底面相等無法堆疊）。故可視為從 3n 個塊中選序列。
2. 按底面長降序、寬降序排序。若長相等則寬大者在前（保證同長度組內寬遞減）。
3. DP：dp[i] 以第 i 塊為底的最大高度。dp[i] = h_i + max{ dp[j] | j < i, l_j > l_i, w_j > w_i }。答案 max(dp[i])。

代碼實現

struct Block { int l, w, h; } b[100];
bool cmp(Block a, Block b) {
    if (a.l == b.l) return a.w > b.w;
    return a.l > b.l;
}
int main() {
    int n, cas=1;
    while (scanf("%d", &n) && n) {
        int cnt=0;
        for(int i=0;i b[i].l && b[j].w > b[i].w)
                    dp[i] = max(dp[i], dp[j] + b[i].h);
            ans = max(ans, dp[i]);
        }
        printf("Case %d: maximum height = %d\n", cas++, ans);
    }
}

關鍵點

• 生成 3 種朝向時，底面長寬排序（長≥寬），避免重複朝向。
• 排序規則確保 DP 只需看前向狀態。
• 無限供應但嚴格遞減導致每種朝向最多用一次，故 0-1 背包式 DP 正確。