地址：http://acm.hdu.edu.cn/showproblem.php?pid=1069
題意：給定若干個木塊長寬高，長寬高可以自己調整，求堆積起來最高的高度。
mark：枚舉所有木塊長寬高可能情況，簡單dp。
代碼：
#include <stdio.h> #include <stdlib.h>typedef struct {int x,y,z; }block;int cmp1(const void *a, const void *b) {block *p = (block *)a, *q = (block *)b;if(p->x != q->x) return q->x - p->x;return q->y - p->y; }int cmp2(const void *a, const void *b) {return *(int *)a - *(int *)b; }int main() {block b[100];int n,m,dp[100],a[3];int i,j,k,max;k = 0;while(scanf("%d", &n), n){for(i = m = 0; i < n; i++){scanf("%d%d%d", a, a+1, a+2);qsort(a, 3, 4, cmp2);if(a[0] == a[1] && a[0] == a[2]){b[m].x = b[m].y = b[m].z = a[0];m++;}else if(a[0] == a[1]){b[m].x = a[2];b[m].y = b[m].z = a[0];m++;b[m].x = b[m].y = a[0];b[m++].z = a[2];}else if(a[1] == a[2]){b[m].x = b[m].z = a[1];b[m].y = a[0];m++;b[m].x = b[m].y = a[1];b[m++].z = a[0];}else{b[m].x = a[2];b[m].y = a[1];b[m++].z = a[0];b[m].x = a[2];b[m].y = a[0];b[m++].z = a[1];b[m].x = a[1];b[m].y = a[0];b[m++].z = a[2];}}qsort(b, m, sizeof(b[0]), cmp1);for(i = max = 0; i < m; i++){dp[i] = b[i].z;for(j = 0; j < i; j++)if(b[i].x < b[j].x && b[i].y < b[j].y)if(dp[i] < dp[j]+b[i].z) dp[i] = dp[j]+b[i].z;if(max < dp[i]) max = dp[i];}printf("Case %d: maximum height = %d\n", ++k, max);}return 0; }
)
