很明显可以根据放不放建边，然后最一遍最长路即是答案
DAG上的动态规划就是根据题目中的二元关系来建一个
DAG，然后跑一遍最长路和最短路就是答案，可以用记忆化搜索的方式来实现
细节：（1）注意初始化数组
（2）搜索的过程中最后记住加入状态本身的值，不然会答案全部为0
#include<cstdio>
#include<algorithm>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 50;
int n, d[MAXN][3], blocks[MAXN][3];void get(int* v, int i, int j)
{int pos = 0;REP(a, 0, 3)if(a != j)v[pos++] = blocks[i][a];
}int dp(int i, int j)
{int& ans = d[i][j];if(ans > 0) return ans;ans = 0;int v[2], v2[2];get(v, i, j);REP(a, 0, n)REP(b, 0, 3){get(v2, a, b);if(v[0] < v2[0] && v[1] < v2[1])ans = max(ans, dp(a, b) );}return ans += blocks[i][j];
}int main()
{int kase = 0;while(~scanf("%d", &n) && n){REP(i, 0, n){REP(j, 0, 3)scanf("%d", &blocks[i][j]);sort(blocks[i], blocks[i] + 3);}memset(d, 0, sizeof(d));int ans = 0;REP(i, 0, n)REP(j, 0, 3)ans = max(ans, dp(i, j));printf("Case %d: maximum height = %d\n", ++kase, ans); }return 0;
}