hdu1069 参考答案

   1 /*
   2 DP
   3 zju 1093,hdu1069,Monkey and Banana
   4 ymc 2008/9/23
   5 题目大意：
   6 用n个尺寸为(x,y,z)的立方体，可以叠出最高的高度。
   7 同一尺寸的立方体无限量供应。
   8 叠加条件：立方体b1可以放在b2上的条件是b2的向上的面的
   9 二维尺寸严格大于b1的向下面的二维尺寸。
  10 分析与解题思路：
  11 因为立方体可以旋转，从而得到不同的基面和高。并且立方体是
  12 无限量供应的，而且叠加是尺寸严格减小的。因而同一个立方体
  13 同样的角度最多只放一次。从而可以把初始的立方体所能得到的
  14 六个旋转后的立方体全部加入初始立方体。下面就无需考虑旋转
  15 与多次使用的条件。
  16 先对立方体从大到小排序，关键字为x,y,z。
  17 令ans[i]为第i个立方体放在最上面时的最大高度。
  18 则ans[i]=Max{ans[j]:b[i]可以放在b[j]上}+b[i].z;
  19 由排序条件，0<=j<i。
  20 
  21 */
  22 #include <iostream>
  23 #include <algorithm>
  24 using namespace std;
  25 const int N=200;
  26 int dir[6][3]={{0,1,2},{0,2,1},{1,0,2},{1,2,0},
  27                {2,0,1},{2,1,0}};//六个旋转方向
  28 struct Block
  29 {
  30     int x,y,z;
  31     bool operator < (const Block &b) const
  32     {  return x>b.x||x==b.x&&y>b.y||x==b.x&&y==b.y&&z>b.z;  }
  33 };
  34 Block b[N];
  35 int ans[N];
  36 int num;
  37 bool Init()
  38 {
  39     int n;
  40     int a[3];
  41     num=0;
  42     scanf("%d",&n);
  43     if(n==0)
  44         return false;
  45     for(int i=0;i<n;i++)
  46     {
  47         scanf("%d %d %d",&a[0],&a[1],&a[2]);
  48         for(int k=0;k<6;k++)
  49         {
  50             b[num].x=a[dir[k][0]];
  51             b[num].y=a[dir[k][1]];
  52             b[num].z=a[dir[k][2]];
  53             num++;
  54         }
  55     }
  56     return true;
  57 }
  58 int DP()
  59 {
  60     sort(b,b+num);
  61     memset(ans,0,sizeof(ans));
  62     ans[0]=b[0].z;
  63     int Max;
  64     for(int i=1;i<num;i++)
  65     {
  66         Max=0;
  67         for(int j=0;j<i;j++)//b[i]能放在b[j]上，并且ans[j]最大
  68         {
  69             if(b[j].x>b[i].x&&b[j].y>b[i].y&&Max<ans[j])
  70                 Max=ans[j];
  71         }
  72         ans[i]=Max+b[i].z;
  73     }
  74     Max=0;
  75     for(int i=0;i<num;i++)
  76         if(ans[i]>Max)
  77             Max=ans[i];
  78     return Max;
  79 }
  80 int main()
  81 {
  82     int t=1;
  83     while(Init())
  84     {
  85         printf("Case %d: maximum height = %d\n",t++,DP());
  86     }
  87 }