HDU 1069 Monkey and Banana：積木堆疊 LIS 變體
題目大意
n ≤ 30 種積木，每種無限供應，尺寸 (x,y,z)。積木可旋轉（任兩維為底，第三維為高）。堆疊規則：上層積木**長寬嚴格小於**下層對應邊。求最高塔高度。
轉化為 LIS 問題
- 每種積木展開 6 種朝向（全排列），得到
6n 個「底面長寬+高度」三元組。
規範：底面長 ≥ 寬（或固定順序），避免重複朝向。
- 按底面長、寬**遞增**排序（長相同則寬遞增）。
- 對高度跑 **LIS 變體**：
dp[i] = height[i] + max{dp[j] | j。
- 答案 =
max(dp[i])。
完整程式碼（C++）
#include
using namespace std;
struct Block { int x, y, h; }; // x≥y 為底面長寬，h 為高
bool cmp(Block a, Block b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
int main() {
int n, cas = 1;
while (cin >> n, n) {
vector blocks;
for (int i=0;i> a >> b >> c;
// 6 種朝向
blocks.push_back({max(a,b), min(a,b), c});
blocks.push_back({max(a,c), min(a,c), b});
blocks.push_back({max(b,c), min(b,c), a});
blocks.push_back({max(b,a), min(b,a), c}); // 重複但無妨
blocks.push_back({max(c,a), min(c,a), b});
blocks.push_back({max(c,b), min(c,b), a});
}
sort(blocks.begin(), blocks.end(), cmp);
int m = blocks.size();
vector dp(m);
int ans = 0;
for (int i=0;i blocks[j].x && blocks[i].y > blocks[j].y)
dp[i] = max(dp[i], dp[j] + blocks[i].h);
ans = max(ans, dp[i]);
}
printf("Case %d: maximum height = %d\n", cas++, ans);
}
return 0;
}
關鍵點
- 積木無限供應 → 同一朝向可重複使用，但排序+LIS 自然處理（同尺寸不會疊加，因需嚴格小於）。
- 底面長寬規範化
x≥y，排序時長優先、寬次之。
n=30 → 180 塊，O(m²) = 32400 極快。
