1 //Accepted    264 KB    0 ms 2 //每种block只有三种方法，且每种放法至多放一次 3 //规定三条边的顺序后 4 //把所有的block按x递增排序，x相同则按y递增排序 5 //然后dp 6 //dp[i]=max(dp[i],dp[j]+height[i]) i可以放到j上 7 #include <cstdio> 8 #include <cstring> 9 #include <iostream>10 #include <algorithm>11 using namespace std;12 const int imax_n = 101;13 struct node14 {15     int x,y,z;16 }p[3*imax_n];17 int dp[3*imax_n];18 int n;19 int max(int a,int b)20 {21     return a>b?a:b;22 }23 int min(int a,int b)24 {25     return a<b?a:b;26 }27 void Dp()28 {29     memset(dp,0,sizeof(dp));30     for (int i=1;i<=3*n;i++)31     {32         for (int j=0;j<i;j++)33         if (p[j].x<p[i].x && p[j].y<p[i].y)34         dp[i]=max(dp[i],dp[j]+p[i].z);35     }36     int ans=0;37     for (int i=1;i<=3*n;i++)38     ans=max(ans,dp[i]);39     printf("%d\n",ans);40 }41 int cmp(struct node p1,struct node p2)42 {43     if (p1.x<p2.x) return 1;44     if (p1.x==p2.x)45     {46         if (p1.y<p2.y) return 1;47     }48     return 0;49 }50 int main()51 {52     int t=0;53     while (scanf("%d",&n),n)54     {55         for (int i=1;i<=n;i++)56         {57             int x,y,z;58             scanf("%d%d%d",&x,&y,&z);59             p[3*i-2].x=min(x,y);60             p[3*i-2].y=max(x,y);61             p[3*i-2].z=z;62             p[3*i-1].x=min(x,z);63             p[3*i-1].y=max(x,z);64             p[3*i-1].z=y;65             p[3*i].x=min(y,z);66             p[3*i].y=max(y,z);67             p[3*i].z=x;68         }69         sort(p+1,p+3*n+1,cmp);70         printf("Case %d: maximum height = ",++t);71         Dp();72     }73     return 0;74 }