首页 > 代码库 > [HDU1069]Monkey and Banana
[HDU1069]Monkey and Banana
题目大意：给你$n$种长方体，要你用这些长方体从下往上叠起来，下面的长方体的长和宽要严格大于上面的。求出最高能搭多高。
思路：先得出可以使用的长方体（长>宽,注意高也可以作为一条长或宽,那么一个长方体至少有3种不同的长宽高），然后根据长排序，接着DP就行了。
具体见代码。
C++ Code:
#include<cstdio>#include<algorithm>#include<cstring>using namespace std;struct cft{ int a,b,h; bool operator<(const cft& rhs)const{ if(a!=rhs.a)return a>rhs.a; return b>rhs.b; }}box[122];int dp[122];int n;int main(){ int o=0; while(~scanf("%d",&n)&&n){ int m=0; for(int i=1;i<=n;i++){//读入、处理 int x[3]; scanf("%d%d%d",&x[0],&x[1],&x[2]); sort(x,x+3); m++; box[m]=(cft){x[2],x[1],x[0]}; m++; box[m]=(cft){x[2],x[0],x[1]}; m++; box[m]=(cft){x[1],x[0],x[2]}; } sort(box+1,box+1+m); memset(dp,0,sizeof(dp)); for(int i=1;i<=m;i++)dp[i]=box[i].h; for(int i=m-1;i>=1;i--)//DP begin for(int j=i+1;j<=m;j++) if(box[i].a>box[j].a&&box[i].b>box[j].b) if(dp[i]<dp[j]+box[i].h)dp[i]=dp[j]+box[i].h;//DP end printf("Case %d: maximum height = %d\n",++o,*max_element(dp+1,dp+1+m)); } return 0;}
[HDU1069]Monkey and Banana
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。