首页 > 代码库 > hdu 1069 Monkey and Banana（记忆搜）
hdu 1069 Monkey and Banana（记忆搜）
题意：
N（不超过30）种木块，每种木块有长、宽、高x,y,z。
木块A可以搭在木块B上当且仅当A的底面长和宽都分别小于B的顶面的长与宽，即不能有超出B的部分。
问垒起来的“木块塔”的最大高度。
思路：
每种木块有6种形态，所以总共有6*N种木块，列张二维关系表，然后记忆搜。
代码：
struct node{ int x,y,z;}b[355];int dp[355];int c;bool mp[355][355];int dfs(int x){ if(dp[x]!=-1) return dp[x]; bool yes = false; rep(i,1,c) if(mp[x][i]){ dp[x] = max( dp[x],dfs(i)+b[x].z ); yes = true; } if(yes==false){ dp[x]=b[x].z; } return dp[x];}int main(){ int n; int T=0; while(scanf("%d",&n)!=EOF && n>0){ rep(i,1,n){ scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].z); } c = n; rep(i,1,n){ b[++c].x=b[i].y; b[c].y=b[i].x; b[c].z=b[i].z; b[++c].x=b[i].x; b[c].y=b[i].z; b[c].z=b[i].y; b[++c].x=b[i].z; b[c].y=b[i].y; b[c].z=b[i].x; b[++c].x=b[i].z; b[c].y=b[i].x; b[c].z=b[i].y; b[++c].x=b[i].y; b[c].y=b[i].z; b[c].z=b[i].x; } mem(mp,false); //mp[i][j]==true：第i种可以放到第j种上 rep(i,1,c){ rep(j,1,c){ if(b[i].x<b[j].x && b[i].y<b[j].y){ mp[i][j]=true; } if(b[i].x>b[j].x && b[i].y>b[j].y){ mp[j][i]=true; } } } mem(dp,-1); int ans = -1; rep(i,1,c){ if(dp[i]==-1){ ans = max( ans,dfs(i) ); }else{ ans = max( ans,dp[i] ); } } printf("Case %d: maximum height = %d\n",++T,ans); } return 0;}
hdu 1069 Monkey and Banana（记忆搜）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。