hdu 1069 Monkey and Banana:
题意:猴子要够到最上方的香蕉通过堆砌起来的箱子,现在又各种的箱子种类为n,给出每种箱子的长宽高,每种的箱子的个数有无限个,因为猴子爬上堆砌起来的箱子要有空的位置可以踩,只能把接触面积小的放在接触面积大的上面,相同的接触面的箱子不能过搭在一起,因此同一种类型的箱子最多只能使用两次,但是要根据箱子的摆放方式,箱子的长宽高(x, y, z),因此箱子有三种的摆放方式(x,
y, z)(x, z, y)(y, z, x)
#include <iostream> #include <algorithm> using namespace std; #define MAX 200 #define max(a, b) a > b ? a : b struct Node { int x, y, z;//长宽高 }; Node b[MAX]; int f[MAX]; int cmp(Node a, Node b) { if (a.x<b.x) return 1; if (a.x==b.x && a.y<b.y) return 1; return 0; } int main() { int i, j, n, c; int x, y, z; c = 0; while (cin>>n && n) { c++; for (i=0,j=0; i<n; i++)//三种摆放方法 { cin>>x>>y>>z; b[j].x = x, b[j].y = y, b[j].z = z; b[j+1].x = x, b[j+1].y = z, b[j+1].z = y; b[j+2].x = y, b[j+2].y = z, b[j+2].z = x; j += 3; } for (i=0; i<n*3; i++)//宽小于长 if (b[i].x<b[i].y) { int t = b[i].x; b[i].x = b[i].y; b[i].y = t; } sort(b, b+n*3, cmp);//按面积大的排序,先比较长,再比较宽 int maxtall=0; for (i=0; i<n*3; i++) { f[i] = b[i].z; for (j=0; j<=i; j++) if (b[i].x>b[j].x && b[i].y>b[j].y) f[i] = max(f[i], f[j]+b[i].z); maxtall = max(maxtall, f[i]); } cout<<"Case "<<c<<": maximum height = "<<maxtall<<endl; } return 0; }