hdu 1069 簡單動態規劃

題目大意：給出n種類型的木塊，求用這些木塊可以堆起的最大高度，要求上邊的木快的長和寬都要嚴格小於下邊。 */ [cpp]   #include<stdio.h>   #include<stdlib.h>   #define N 95   int f[N];  //f[N]記錄加上第i個木塊後的最大高度   struct X   {       int x,y,z;   }block[N];   int cmp(const struct X* a,const struct X* b)   {       if((*a).x!=(*b).x)           return (*a).x-(*b).x;       else           return (*a).y-(*b).y;   }   int main()   {       int T,n,a,b,c,i,j,temp,tallest;       T=1;       while(scanf("%d",&n),n){           for(i=0,j=0;j<n;j++){       //每種木塊可以有三種放法               scanf("%d%d%d",&a,&b,&c);               block[i].x=a; block[i].y=b; block[i].z=c;               block[i+1].x=a; block[i+1].y=c; block[i+1].z=b;               block[i+2].x=c; block[i+2].y=b; block[i+2].z=a;               i+=3;           }           for(i=0;i<n*3;i++){          //找出每種木塊的長和寬               if(block[i].x<block[i].y){                   temp=block[i].x;                   block[i].x=block[i].y;                   block[i].y=temp;               }           }           qsort(block,n*3,sizeof(block[0]),cmp); //先按木塊的"長"升序排列，"長"相等時再按"寬"升序排列           for(i=0,tallest=0;i<3*n;i++){    //將f[i]初始化為第i個的高度，計算f[i]時，遍歷0—>i，找出放上第i個木塊時的最大高度。               f[i]=block[i].z;               for(j=0;j<=i;j++){                   if(block[i].x>block[j].x&&block[i].y>block[j].y){                       f[i]=max(f[i],f[j]+block[i].z);                   }                   tallest=max(tallest,f[i]);               }           }           printf("Case %d: maximum height = %d\n",T++,tallest);       }       return 0;   }