题意
一组研究人员正在设计一项实验,以测试猴子的智商。他们将挂香蕉在建筑物的屋顶,同时,提供一些砖块给这些猴子。如果猴子足够聪明,它应当能够通过合理的放置一些砖块建立一个塔,并爬上去吃他们最喜欢的香蕉。
研究人员有n种类型的砖块,每种类型的砖块都有无限个。第i块砖块的长宽高分别用xi,yi,zi来表示。 同时,由于砖块是可以旋转的,每个砖块的3条边可以组成6种不同的长宽高。
在构建塔时,当且仅当A砖块的长和宽都分别小于B砖块的长和宽时,A砖块才能放到B砖块的上面,因为必须留有一些空间让猴子来踩。
你的任务是编写一个程序,计算猴子们最高可以堆出的砖块们的高度。
解题
将每个砖块看作六个。将这6n个砖块按照长度升序排序排序、长度相等则宽带升序排。这样,得到的序列中的升序子序列(升序的要求是:后一个比前一个的长度和宽度都大)就是一个合法的塔。要求塔最高,即求最长上升子序列。
设dp[i]表示以第i个数作为序列的结尾所得到的上升子序列的塔高。
状态转移方程:dp[i]=max{dp[j]+h[i],1<=j<=i-1}.h[i]表示第i块砖块的高度。
AC代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;struct node
{int x,y,z;node(int x,int y,int z):x(x),y(y),z(z){}node(){}bool operator<(const node &o)const{return x<o.x || x==o.x&&y<o.y;}
}a[200];
int dp[200];
int main()
{int n,cnt,kase=0;while(~scanf("%d",&n),n){int x,y,z;cnt=0;memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){scanf("%d%d%d",&x,&y,&z);a[++cnt]=node(x,y,z);a[++cnt]=node(x,z,y);a[++cnt]=node(y,x,z);a[++cnt]=node(y,z,x);a[++cnt]=node(z,x,y);a[++cnt]=node(z,y,x);}sort(a+1,a+1+cnt);// for(int i=1;i<=cnt;i++)// printf("%d %d %d\n",a[i].x,a[i].y,a[i].z);int ans=a[1].z;for(int i=2;i<=cnt;i++){dp[i]=a[i].z;for(int j=1;j<i;j++){if(a[j].x<a[i].x && a[j].y<a[i].y)dp[i]=max(dp[i],dp[j]+a[i].z);}ans=max(ans,dp[i]);}printf("Case %d: maximum height = ",++kase);printf("%d\n",ans);}return 0;
}