题目:
437 - The Tower of Babylon
思路:
一个立方体最多使用三次,就不可能再用。输入的一个立方体可以变成三个确定长宽高的立方体。然后将这些立方体先做预处理,如果立方体j能够放在立方体i上面,那么i到j有一条有向边。这样只要在这个有向无环图里面搜索就可以。
其他见代码及注释。
AC代码:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 90 +5;
int n;
struct blocks{
int x, y, z;
}b[maxn];
bool ok[maxn][maxn]; //记录i是否可以放在j上
int dp[maxn]; //记录当前最大高度
int DP(int i, int pos){
if(dp[i]>0) return dp[i]; //如果dp[i]已经搜索过,直接返回dp[i]
dp[i] = b[i].z; //否则记录当前block的高度为dp[i]
for(int j=0; j<pos; j++){ //对所有block都搜索一遍
if(ok[i][j]){ //如果j可以放在i上面
dp[i] = max(dp[i], DP(j, pos) + b[i].z); //进行递归搜索,及更新dp值
}
}
return dp[i]; //返回得到的dp[i]值
}
int main(){
int kase = 0;
int l, w, h;
while(scanf("%d", &n)==1 && n){
//初始化 dp[]和ok[][]数组
for(int i=0; i<maxn; i++){
dp[i] = 0;
for(int j=0; j<maxn; j++){
ok[i][j] = 0;
}
}
int pos = 0;
for(int i=0; i<n; i++){
scanf("%d%d%d", &l, &w, &h);
//每种block都有三种放置方式,在这里假定x比y大,方便后面作图
b[pos].x = l > w ? l : w, b[pos].y = l > w ? w : l, b[pos++].z = h;
b[pos].x = l > h ? l : h, b[pos].y = l > h ? h : l, b[pos++].z = w;
b[pos].x = h > w ? h : w, b[pos].y = h > w ? w : h, b[pos++].z = l;
}
for(int i=0; i<pos; i++){
for(int j=0; j<pos; j++){
if(b[i].x > b[j].x && b[i].y > b[j].y){ //满足放置规则
ok[i][j] = 1;
}
}
}
int ans = 0;
for(int i=0; i<pos; i++){
ans = max(ans, DP(i, pos)); //搜索并记录最大值
}
printf("Case %d: maximum height = ", ++kase);
printf("%d\n", ans);
}
return 0;
}