www.pudn.com > zhejiang_university_acm_onlinejudge_code.rar > zp1093_dp.cpp

//--------------------------------------------------------------------------- 
 
#include  
#pragma hdrstop 
 
//--------------------------------------------------------------------------- 
 
#pragma argsused 
#include  
#include  
using namespace std; 
 
struct typec 
{ 
  int ht,lg,sh; 
}; 
typec box[100]; 
 
int pbox[32][4]; 
int r[100][100],lar[100]; 
short lp[1000000]; 
 
int main(int argc, char* argv[]) 
{ 
  int cs,n,t,i,j,k,s,max,ht,lars; 
  cin>>n; 
  cs=0; 
  while(n) 
  { 
    s=0;lars=0; 
    for (i=0;i>pbox[i][0]>>pbox[i][1]>>pbox[i][2]; 
      for (k=0;k<2;k++) 
        for (j=k+1;j<3;j++) 
          if (pbox[i][k]>pbox[i][j]) 
          { 
            t=pbox[i][j]; 
            pbox[i][j]=pbox[i][k]; 
            pbox[i][k]=t; 
          } 
      if (pbox[i][0]==pbox[i][1] 
       || pbox[i][1]==pbox[i][2]) 
        if (pbox[i][0]==pbox[i][2]) 
        { 
          box[s].ht=pbox[i][0]; 
          box[s].lg=pbox[i][0]; 
          box[s++].sh=pbox[i][0]; 
          lar[lars++]=pbox[i][0]; 
        } 
        else 
        { 
          box[s].ht=pbox[i][2]; 
          box[s].lg=pbox[i][1]; 
          box[s++].sh=pbox[i][0]; 
          box[s].ht=pbox[i][0]; 
          box[s].lg=pbox[i][2]; 
          box[s++].sh=pbox[i][1]; 
          lar[lars++]=pbox[i][0]; 
          lar[lars++]=pbox[i][2]; 
        } 
      else 
      { 
        box[s].ht=pbox[i][2]; 
        box[s].lg=pbox[i][1]; 
        box[s++].sh=pbox[i][0]; 
        box[s].ht=pbox[i][0]; 
        box[s].lg=pbox[i][2]; 
        box[s++].sh=pbox[i][1]; 
        box[s].ht=pbox[i][1]; 
        box[s].lg=pbox[i][2]; 
        box[s++].sh=pbox[i][0]; 
        lar[lars++]=pbox[i][0]; 
        lar[lars++]=pbox[i][1]; 
        lar[lars++]=pbox[i][2]; 
      } 
    } 
    for (i=0;ilar[j]) 
        { 
          t=lar[i]; lar[i]=lar[j]; lar[j]=t; 
        } 
    for (i=0;i0;i--) 
      for (j=lars;j>0;j--) 
        if (r[i][j]) 
          for (k=0;kr[lp[box[k].lg]][lp[box[k].sh]]) 
            { 
              r[lp[box[k].lg]][lp[box[k].sh]]=r[i][j]+box[k].ht; 
              if (r[lp[box[k].lg]][lp[box[k].sh]]>max) 
                max=r[lp[box[k].lg]][lp[box[k].sh]]; 
            } 
 
    cout<<"Case "<<++cs<<": maximum height = "<>n; 
  } 
  return 0; 
} 
 
//---------------------------------------------------------------------------