一道DAGdp
思路
首先要明确，我们要求的是最长路，图可以根据立方体间的关系来建，如果这个立方体可以放在另一个上面，就从代表这个立方体的点向那个点连一条有向边。
因为两条边都是严格小于下面的立方体的，所以这个图一定是个有向无环图（DAG）。
另外，由于每个立方体有三种高，所以总共会有3n种不同的立方体，空间要开三倍。
这里我是用的邻接矩阵建图+记忆化搜索；
代码如下（附注释）
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,d[100][3],kase,sh[31][3];//d是记忆化用的数组
int tot;
bool G[100][100];//因为只要判断能不能搭上去，所以只用bool，节省空间
struct node{
int x,y,su,h;//x,y,h分别代表这个立方体的长宽高，su代表高的类型
}S[100];
int dp(int num,int su)//num是当前立方体的编号，su意思同上
{
int& ans=d[num][su];
if(ans>0)return ans;//记忆化
ans=S[num].h;
for(int i=1;i<=tot;i++)
if(G[num][i])ans=max(ans,dp(i,S[i].su)+S[num].h);//如果有连边，就更新
return ans;
}
int main()
{
while(1)
{
scanf("%d",&n);
if(!n)break;
memset(d,0,sizeof(d));
memset(G,0,sizeof(G));//多组数据记得初始化
int maxn=-1;tot=0;
for(int i=1;i<=n;i++)scanf("%d%d%d",&sh[i][0],&sh[i][1],&sh[i][2]);//读入三种边
printf("Case %d: maximum height = ",++kase);
for(int i=1;i<=n;i++)
{
for(int j=0;j<3;j++)//记录每一种类型的立方体
{
S[++tot].su=j;
S[tot].h=sh[i][j];
if(j==0)
S[tot].x=sh[i][1],S[tot].y=sh[i][2];
if(j==1)
S[tot].x=sh[i][0],S[tot].y=sh[i][2];
if(j==2)
S[tot].x=sh[i][0],S[tot].y=sh[i][1];
}
}
for(int i=1;i<=tot;i++)//建图
{
for(int j=1;j<=tot;j++)
{
if(i!=j&&((S[i].x<S[j].x&&S[i].y<S[j].y)||(S[i].x<S[j].y&&S[i].y<S[j].x)))
{
G[i][j]=1;
}
}
}
for(int i=1;i<=tot;i++)
{
for(int j=0;j<3;j++)
maxn=max(maxn,dp(i,j));
}
printf("%d
",maxn);
}
return 0;
}