首页 > 代码库 > UVa437,The Tower of Babylon
UVa437,The Tower of Babylon
转:http://blog.csdn.net/wangtaoking1/article/details/7308275
题意为输入若干种立方体(每种若干个),然后将立方体堆成一个塔,要求接触的两个面下底面的长宽分别严格大于上底面,求塔的最大高度。
将每种立方体的各种摆放形式均视为不同的立方体,并存起来。再将所有立方体按照下底面的面积从小到大排序(因为在塔上面的立方体的底面积一定比下面的小),然后只需求该序列的最大上升子序列的长度即可。
#include <iostream>#include <cstdio>#include <string.h>#include <algorithm>using namespace std;struct node //记录每个立方体的长宽高{ int x,y,z; void f(int a, int b,int c) { x=a; y=b; z=c; }}st[200];bool comp(node a, node b) //按立方体的底面积从小到大进行排序{ if( a.x*a.y <b.x*b.y ) return 1; return 0;}int n,m, x,y,z,dp[200];int main(){ int flag =1; while( scanf("%d", &n) &&n ) { m=0; int i,j; for( i=0; i<n; i++) { scanf("%d%d%d", &x, &y, &z); st[ m++].f(x,y,z); //将6种立方体均保存起来 st[ m++].f(x,z,y); st[ m++].f(y,z,x); st[ m++].f(y,x,z); st[ m++].f(z,x,y); st[ m++].f(z,y,x); } sort( st, st+m, comp); int t=0; for( i=0; i<m; i++) //求最长上升子序列 { dp[i] =st[i].z; for( j=0; j<i; j++) if( st[i].x >st[j].x && st[i].y >st[j].y ) dp[i] =max( dp[i], dp[j] +st[i].z); if( dp[i] >t) t =dp[i]; } printf("Case %d: maximum height = %d\n",flag++,t); } return 0;}
该方法要比紫薯上提供的方法要好的多。清晰易懂。
题意虽说有若干个立方体,但仔细想想,答案说生成的序列中最多可能包含3个同一个立方体(再仔细想想,应该是两个,但是我们还需要看成3个),故将一个立方体拓展成三个立方体即可。
将所有立方体按照下底面的面积从小到大排序(其实也可以对长度一级排序,对宽度二级排序),然后用if( st[i].x >st[j].x && st[i].y >st[j].y ) 判断能否状态转移
UVa437,The Tower of Babylon
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。