题意:
把给定尺寸的长方体 ( 数量不限 ) 叠在一起 , 能叠加的条件是 ,
上面一个长方体的长宽比下面一个长方体的长宽短都短 ,
或者一边相等 , 另一边较短 , 长方体可以任意面朝下摆放 , 求这些长方体能够叠成的最高的高度 .
分析:
简单DP
先数据有序化一下。
然后,设f[i] = max{ f[j] + rec[i].h} (j<i,blocks[i]能放在blocks[j]上)
code:
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;struct node{int x;int y;int h;bool operator <(const node& t)const{return x>t.x||(x==t.x&&y>t.y);}} rec[100];int main(){int n;int i, j, max;int k;int x, y, z;int dp[100];int T = 1;while(scanf("%d",&n),n){k = 0;for(i=0; i<n; i++){scanf("%d%d%d",&x,&y,&z);if(x>y) rec[k].x = x, rec[k].y = y;else rec[k].x = y, rec[k].y = x;rec[k++].h = z;if(x>z) rec[k].x = x, rec[k].y = z;else rec[k].x = z, rec[k].y = x;rec[k++].h = y;if(z>y) rec[k].x = z, rec[k].y = y;else rec[k].x = y, rec[k].y = z;rec[k++].h = x;}sort(rec,rec+k);dp[0] = rec[0].h;for(i=1; i<k; i++){max = 0;for(j=i-1; j>=0; j--){if( (rec[j].y>rec[i].y&&rec[j].x>rec[i].x)||(rec[j].y>rec[i].x&&rec[j].x>rec[i].y) ){if(dp[j]>max)max = dp[j];}}dp[i] = max + rec[i].h;}max = 0;for(i=0; i<k; i++)if(dp[i]>max)max = dp[i];printf("Case %d: maximum height = %d\n",T++,max);}return 0;}