题意：
有n种长宽高为x,y,z的砖头，每种都有无数个。砖头可以用不同姿势的方向来盖。
砖头a以某种姿势可以盖在砖头b上，当且仅当a的底部的长宽都要比b的底部长宽要小。
问最高可以建多高？
思路：
其实就是白书DAG上dp一个基础题。归结为矩形嵌套问题，状态转移和三角形状态转移一样。
对于一个x,y,z砖头，它可以有3中姿势放置。注意矩形可以旋转90度，所以宽高位置没影响，主要在不同值上。
(前两个为地面，后一个为高)
x, y, z
x, z, y
y, z, x
把每种姿势都记录下来，变成了有3*n种固定姿势的砖头。
然后建图， 注意双向图，mp[i][j] = true,表示砖头i可以盖在砖头j上，反之亦然，从外圈到内圈
#include <bits/stdc++.h> using namespace std; const int maxn = 100; bool mp[maxn][maxn]; int d[maxn]; int n; struct Node { int x,y,h; }node[maxn]; bool check(int i,int j) { return node[i].x<node[j].x && node[i].y<node[j].y || node[i].x < node[j].y &&node[i].y < node[j].x; } int dfs(int u) { if(d[u]!=-1) { return d[u]; } //当前的自己的高度 d[u] = node[u].h; for(int i = 0; i < n; i++) { if(mp[u][i]) { //d[u] = max(d[u],dfs(i)+node[u].h) //一开始这样写，循环每次循环d[u]就变了，所以加的不是这一层的高度，而是累加了 //遍历当前u为起点的所有可到达的下一个"状态" d[u] = max(d[u],dfs(i)+node[u].h); } } return d[u]; } int main() { // freopen("in.txt","r",stdin); int casen; casen = 0; while(scanf("%d",&n)&&n) { for(int i = 0; i < n; i++) { scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].h); node[n+i].x = node[i].y; node[n+i].y = node[i].h; node[n+i].h = node[i].x; node[n*2+i].x = node[i].x; node[n*2+i].y = node[i].h; node[n*2+i].h = node[i].y; } n *= 3; memset(mp,false,sizeof(0)); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { mp[i][j] = check(i,j); } } memset(d,-1,sizeof(d)); int ans = 0; for(int i = 0; i < n; i++) { ans = max(ans,dfs(i)); } printf("Case %d: maximum height = %d ",++casen,ans); } return 0; }