[cpp] 描述：給出n種長方體，每種長方體無數個，將這些長方體按照長和寬依次遞減的趨勢依次增加高度，求最大的高度是多少 #include <cstdio> #include <cstdlib> int n,m,t,sum; int arr[100][3]; int max(int x,int y) { return x>y?x:y; } void swap(int &x,int &y) { if(x>y) { int temp=x; x=y; y=temp; } } int cmp(const void *p1,const void *p2) { if(((int *)p1)[1]>((int *)p2)[1]) return 1; else if(((int *)p1)[1]<((int *)p2)[1]) return -1; else { if(((int *)p1)[2]>((int *)p2)[2]) return 1; else return -1; } } int main() { // freopen("a.txt","r",stdin); t=1; while(scanf("%d",&n)!=EOF) { if(!n) break; n*=3; sum=0; for(int i=0; i<n; i++) { scanf("%d %d %d",&arr[i][0],&arr[i][1],&arr[i][2]); sum=max(max(max(arr[i][0],arr[i][1]),arr[i][2]),sum); arr[i+1][0]=arr[i][1],arr[i+1][1]=arr[i][2],arr[i+1][2]=arr[i][0]; arr[i+2][0]=arr[i][2],arr[i+2][1]=arr[i][0],arr[i+2][2]=arr[i][1]; swap(arr[i][1],arr[i][2]); swap(arr[i+1][1],arr[i+1][2]); swap(arr[i+2][1],arr[i+2][2]); i+=2; } qsort(arr,n,sizeof(arr[0]),cmp); for(int i=n-2; i>=0; i--) { m=0; for(int j=n-1; j>i; j--) if(arr[i][1]<arr[j][1]&&arr[i][2]<arr[j][2]&&m<arr[j][0]) m=arr[j][0]; arr[i][0]+=m; if(arr[i][0]>sum) sum=arr[i][0]; } printf("Case %d: maximum height = %d\n",t++,sum); } return 0; }
