A group of researchers are designing an experiment to test the IQ of a monkey. They will hang a banana at the roof of a building, and at the mean time, provide the monkey with some blocks. If the monkey is clever enough, it shall be able to reach the banana by placing one block on the top another to build a tower and climb up to get its favorite food.
The researchers have n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions (xi, yi, zi). A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height.
They want to make sure that the tallest tower possible by stacking blocks can reach the roof. The problem is that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the corresponding base dimensions of the lower block because there has to be some space for the monkey to step on. This meant, for example, that blocks oriented to have equal-sized bases couldn't be stacked.
Your job is to write a program that determines the height of the tallest tower the monkey can build with a given set of blocks.
Input
The input file will contain one or more test cases. The first line of each test case contains an integer n,
representing the number of different blocks in the following data set. The maximum value for n is 30.
Each of the next n lines contains three integers representing the values xi, yi and zi.
Input is terminated by a value of zero (0) for n.
Output
For each test case, print one line containing the case number (they are numbered sequentially starting from 1) and the height of the tallest possible tower in the format "Case case: maximum height = height".
Sample Input
1 10 20 30 2 6 8 10 5 5 5 7 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 5 31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 0
Sample Output
Case 1: maximum height = 40 Case 2: maximum height = 21 Case 3: maximum height = 28 Case 4: maximum height = 342
题意：给你n个长方体以及每个的长宽高，这些长方体的数量无限且可以任意旋转。长方体可以叠放在长和宽都比它大的长方体上（不能都相等），问最高能叠多高。
思路
（1）输入问题；这不是普通的输入，因为一个长方体可以用多次
但是实际上最多用3次 6个面两两重复（其实刚开始我还写的两个，因为我觉得 一个长方体最大面和最小面能用一下，另一个面和最大面，最小面有一边相等，这样想是错误的）
（2）这样一个长方体变成3个长方体，选长方体使其最高，乍一看像背包，一件物品选或者不选，但是，天真的我忘了一点，背包选物品是没有顺序，这个物品可以放在最后判断选不选，也可以放在前面，但是这题不一样，先选和后选是不一样的，先选可能能选上，但是后选就不一定能不能选上了，这一点差别导致思想千差万别
（3）既然要取最大值，那么最好还是把最大的放后面，这样我们从头开始找（你是不是想到了贪心），但是贪心是做不好这道题的，
如果遇到相同的长（或者宽），那么你要选择哪一个？而且即使选择了最高的（假设是第一个，没选的是第二个），你能保证下一次不会出一个宽（或者长）比第一个长，比第二个短，而且高特别高；那么只能动态规划了，动态规划会记录前面所有的情况的最优解，用前面的多个选一个推出下一个，贪心只能用最近的一个推下一个
这就是动规和贪心的本质区别
这是我思考的思路，写出来供大家思考
下面是题的思路
（1）先输入后，一个变6个，然后排一下序，从大到小（这样方便）
（2）然后就是 最长单调递减子序列
那么为什么会联系到最长单调递减子序列那？
对，我们排序后，长方体都从小到大排好序了，我们要找最高，那么其实我们就是把单调递减子序列的 最多，换成了最高，
下面分析一下最长单调递减子序列的动态
其实说简单点就一句话；
从头开始遍历，每遍历一个，找找前面的，有没有比这个大的，如果有，那么找出一个结果最大的（即最优解） 以这个为上一个状态，在这个状态上加上当前的值，就是当前的最优解；
C++版本一
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int t;
int n,ant;
int maxh;
int x,y,z;
struct shape{
int l,w,h;
}a[200];
bool cmp(shape a,shape b)
{
if (a.l == b.l)
return a.w > b.w;
return a.l > b.l;
}
void PushUp(int t1,int t2,int t3)
{
a[ant].h = t3;
a[ant].l = t1;
a[ant].w = t2;
ant++;
a[ant].h = t3;
a[ant].l = t2;
a[ant].w = t1;
ant++;
a[ant].h = t2;
a[ant].l = t1;
a[ant].w = t3;
ant++;
a[ant].h = t2;
a[ant].l = t3;
a[ant].w = t1;
ant++;
a[ant].h = t1;
a[ant].l = t2;
a[ant].w = t3;
ant++;
a[ant].h = t1;
a[ant].l = t3;
a[ant].w = t2;
ant++;
}
int main()
{ t=0;
while(scanf("%d",&n)!=EOF){
if(n==0) break;
t++;
maxh=0;
ant=1;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&x,&y,&z);
PushUp(x,y,z);
}
sort(a+1,a+6*n+1,cmp);
int dp[200];
int ans=0;
for(int i=1;i<=6*n;i++){
dp[i]=a[i].h;
for(int j=i-1;j>=0;j--){
if(a[i].l<a[j].l&&a[i].w<a[j].w){
dp[i]=max(dp[i],dp[j]+a[i].h);
}
}
ans=max(dp[i],ans);
}
printf("Case %d: maximum height = %d\n",t,ans);
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
/*
HDU1069Monkey and Banana
题目：给出一些长方体，然后让你把他堆成塔，
要求下面的塔的要比上面的塔大（长和宽），
而且每一种长方体的数量都是无限的。
此题目考察到动态规划里的最长有序子序列，
*/
#include<stdio.h>
#include<algorithm>
const int MAXN=200;
using namespace std;
struct Block
{
int x,y,high;
int dp;//该箱子在最下面时的最大高度
}b[MAXN];
bool cmp(Block a,Block b)//用sort函数排序，先按x后按y升序
{
if(a.x<b.x) return 1;
else if(a.x==b.x&&a.y<b.y) return 1;
else return 0;
}
int main()
{
int n,i,x,y,z,j,k;
int iCase=0;
while(scanf("%d",&n),n)
{
iCase++;
k=0;
while(n--)
{
scanf("%d%d%d",&x,&y,&z);
//把给出的block放置的所有可能放进block[]中，这样就可以解决有无限块的问题
if(x==y)
{
if(y==z)//三个相等，放一个就够了
{
b[k].x=x;b[k].y=y;b[k].high=z;b[k].dp=b[k].high;k++;
}
else //x==y!=z时三种放法
{
b[k].x=x;b[k].y=y;b[k].high=z;b[k].dp=b[k].high;k++;
b[k].x=z;b[k].y=y;b[k].high=x;b[k].dp=b[k].high;k++;
b[k].x=y;b[k].y=z;b[k].high=x;b[k].dp=b[k].high;k++;
}
}
else
{
if(y==z)//三种放法
{
b[k].x=x;b[k].y=y;b[k].high=z;b[k].dp=b[k].high;k++;
b[k].x=y;b[k].y=x;b[k].high=z;b[k].dp=b[k].high;k++;
b[k].x=y;b[k].y=z;b[k].high=x;b[k].dp=b[k].high;k++;
}
else if(x==z)
{
b[k].x=x;b[k].y=y;b[k].high=z;b[k].dp=b[k].high;k++;
b[k].x=y;b[k].y=x;b[k].high=z;b[k].dp=b[k].high;k++;
b[k].x=x;b[k].y=z;b[k].high=y;b[k].dp=b[k].high;k++;
}
else//三个不等6种放法
{
b[k].x=x;b[k].y=y;b[k].high=z;b[k].dp=b[k].high;k++;
b[k].x=y;b[k].y=x;b[k].high=z;b[k].dp=b[k].high;k++;
b[k].x=x;b[k].y=z;b[k].high=y;b[k].dp=b[k].high;k++;
b[k].x=z;b[k].y=x;b[k].high=y;b[k].dp=b[k].high;k++;
b[k].x=y;b[k].y=z;b[k].high=x;b[k].dp=b[k].high;k++;
b[k].x=z;b[k].y=y;b[k].high=x;b[k].dp=b[k].high;k++;
}
}
}
sort(b,b+k,cmp);
int maxh=0;
for(i=1;i<k;i++)
{
for(j=0;j<i;j++)
if(b[i].x>b[j].x&&b[i].y>b[j].y)
b[i].dp=max(b[j].dp+b[i].high,b[i].dp);
if(b[i].dp>maxh)maxh=b[i].dp;
}
printf("Case %d: maximum height = %d\n",iCase,maxh);
}
return 0;
} C++版本三
#include<cstdio>
#include<algorithm>
using namespace std;
struct stu
{
int l,w,h;
}st[185];
bool cmp(stu a,stu b) //从顶往下判断所以从小往大排序
{
if(a.l != b.l)
return a.l < b.l;
else
return a.w < b.w;
}
int main()
{
int k=1;
int dp[185]; //dp[i]表示从顶开始到第i个木块的高度
int n,a,b,c,max0,num;
while(scanf("%d",&n) && n)
{
int i,j;
num=0;
for(i = 1 ; i <= n ; i++)
{
scanf("%d %d %d",&a,&b,&c);
st[num].l=a,st[num].w=b,st[num++].h=c; //每个木块有三种放法
st[num].l=a,st[num].w=c,st[num++].h=b;
st[num].l=b,st[num].w=a,st[num++].h=c;
st[num].l=b,st[num].w=c,st[num++].h=a;
st[num].l=c,st[num].w=a,st[num++].h=b;
st[num].l=c,st[num].w=b,st[num++].h=a;
}
sort(st,st+num,cmp);
for(i = 0 ; i < num ; i++)
{
dp[i]=st[i].h;
}
for(i = 0 ; i < num ; i++)
{
for(j = 0 ; j < i ; j++)
{
if(st[j].l < st[i].l && st[j].w < st[i].w && dp[j]+st[i].h > dp[i])
{
dp[i]=dp[j]+st[i].h;
}
}
}
sort(dp,dp+num);
printf("Case %d: maximum height = ",k++);
printf("%d\n",dp[num-1]);
}
return 0;
} C++版本四
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0);
const int N=190;
struct info
{
int x;
int y;
int z;
bool operator<(const info &t)const
{
if(x!=t.x)
return x<t.x;
return y<t.y;
}
info(int xx,int yy,int zz):x(xx),y(yy),z(zz){}
info(){}
};
vector<info>arr;
int dp[N];
int main(void)
{
int n,i,j,x,y,z;
int q=1;
while (~scanf("%d",&n)&&n)
{
CLR(dp,0);
arr.clear();
for (i=0; i<n; ++i)
{
scanf("%d%d%d",&x,&y,&z);
arr.push_back(info(x,y,z));
arr.push_back(info(x,z,y));
arr.push_back(info(y,x,z));
arr.push_back(info(y,z,x));
arr.push_back(info(z,x,y));
arr.push_back(info(z,y,x));
}
sort(arr.begin(),arr.end());
int SZ=arr.size();
for (i=0; i<SZ; ++i)
{
int pre_max=0;
for (j=0; j<i; ++j)
{
if(arr[j].x<arr[i].x&&arr[j].y<arr[i].y&&dp[j]>pre_max)
pre_max=dp[j];
}
dp[i]=pre_max+arr[i].z;
}
printf("Case %d: maximum height = %d\n",q++,*max_element(dp,dp+SZ));//n^2算法这里就要取max，之前搞混了直接输出最后一个导致WA
}
return 0;
}
京公网安备 11010502036488号