uva 437 动态规划 lrj - P269

本文主要是介绍uva 437 动态规划 lrj - P269，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给出不超过30个立方体，每一种有无穷多个。

要求这些立方体堆成一个尽量搞的柱子，使得每一个立方体下面的立方体的底面长宽都大于上面的底面长宽

题解：

很明显我们可以将每个立方体当做3个或者6个不一样的不可以旋转的长方体

下面代码当做6个，是为了方便计算，这样在判断的过程中不需要加太多条件

而且数据量不大，可以这样做

dp思想：

01背包的思想，放与不放，最后求一个最大值就行了

不能直接取dp【m-1】，因为我们不知道最后一个立方体用了还是没有用

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;struct node
{int x,y,z;node(){}node(int x_,int y_,int z_){x=x_,y=y_,z=z_;}
}blocks[200];
int dp[200];bool cmp(node x1,node x2){return x1.x*x1.y<x2.x*x2.y;
}int main()
{int cases=1,n,a,b,c;//freopen("in.txt","r",stdin);while(scanf("%d",&n),n){int m=0;for(int i=1;i<=n;i++){scanf("%d%d%d",&a,&b,&c);blocks[m++]=node(a,b,c);blocks[m++]=node(b,a,c);blocks[m++]=node(c,b,a);blocks[m++]=node(b,c,a);blocks[m++]=node(a,c,b);blocks[m++]=node(c,a,b);}sort(blocks,blocks+m,cmp);int ans=0;for(int i=0;i<m;i++){dp[i]=blocks[i].z;for(int j=0;j<i;j++){if(blocks[i].x>blocks[j].x&&blocks[i].y>blocks[j].y)dp[i]=max(dp[i],dp[j]+blocks[i].z);}ans=max(ans,dp[i]);}printf("Case %d: maximum height = %d\n",cases++,ans);}return 0;
}

这篇关于uva 437 动态规划 lrj - P269的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---