UVA437 The Tower of Babylon 动态规划

题意：给你N种立方体，每种立方体个数不限，让你堆塔，求塔最大高度，堆塔的条件是 每一个立方体的长和宽 必须严格大于它下面的立方体的长和宽，因为每个立方体个数无限，所以必须要进行排序了，不需要按照堆塔的条件来排序，可以按照底面积的大小来排，原因很简单，还有因为立方体个数无限，外加堆塔条件限制，其实就是每一种立方体又可以演变成 六种立方体，因为没有固定 哪个是高  宽 长，都处理好以后，一看就是一个 类似于 LIS 的问题，只不过长度 每次的+1 变成了+当前立方体的高罢了，敲起来很快

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long

#define eps 1e-7

#define inf 0xfffffff
//const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;

//#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin)  
//#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) 

int dp[100000 + 5];

struct Node {
	int l,w,h;
	void cal(int x,int y,int z) {
		l = x,w = y, h = z; 
	}
}node[100000 + 5];

void clear() {
	memset(dp,0,sizeof(dp));
	memset(node,0,sizeof(node));
}

bool cmp(Node x,Node y) {
	return x.l * x.w < y.l * y.w;
}

int main() {
	int n;
	int Case = 0;
	while(scanf("%d",&n),n) {
		clear();
		int tot = 0;
		for(int i=1;i<=n;i++) {
			int x,y,z;
			scanf("%d %d %d",&x,&y,&z);
			node[++tot].cal(x,y,z);
			node[++tot].cal(x,z,y);
			node[++tot].cal(y,x,z);
			node[++tot].cal(y,z,x);
			node[++tot].cal(z,x,y);
			node[++tot].cal(z,y,x);
		}
		sort(node + 1,node + tot,cmp);
		for(int i=1;i<=tot;i++)
			dp[i] = node[i].h;
		int ans = 0;
		for(int i=2;i<=tot;i++) {
			for(int j=1;j<i;j++) {
				if(node[i].l > node[j].l && node[i].w > node[j].w)
					dp[i] = max(dp[i],dp[j] + node[i].h);
			}
			if( ans < dp[i])
				ans = dp[i];
		}
		printf("Case %d: maximum height = %d\n",++Case,ans);
	}
	return EXIT_SUCCESS;
}

UVA437 The Tower of Babylon 动态规划

原文：http://blog.csdn.net/yitiaodacaidog/article/details/19087371