dp[i] 表示以第i塊木塊放在最頂端得到的最高高度

dp[i] = max{dp[i] , dp[j]+block[i].h} j<i

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 using namespace std;
 6 #define N 1000
 7 struct Block{
 8     int x , y , h;
 9 };
10 
11 bool cmp(const Block &a,const Block &b){
12     if(a.x>b.x) return true;
13     if(a.x==b.x&&a.y>b.y) return true;
14     return false;
15 }
16 
17 int k , dp[N];
18 Block block[N];
19 
20 int main()
21 {
22   //  freopen("a.in" , "r" , stdin);
23     int cas = 0;
24     int n , a , b , h;
25     while(~scanf("%d" , &n)){
26         if(n == 0) break;
27         k = 0;
28         memset(dp,0,sizeof(dp));
29         for(int i = 0 ; i < n ; i++){
30             scanf("%d%d%d" , &a , &b , &h);
31             block[k].x = a , block[k].y = b , block[k++].h = h;
32             block[k].x = b , block[k].y = a , block[k++].h = h;
33             block[k].x = a , block[k].y = h , block[k++].h = b;
34             block[k].x = h , block[k].y = a , block[k++].h = b;
35             block[k].x = b , block[k].y = h , block[k++].h = a;
36             block[k].x = h , block[k].y = b , block[k++].h = a;
37         }
38 
39         sort(block , block+k , cmp);
40 
41         for(int i = 0 ; i<k ; i++){
42             dp[i] = block[i].h;
43             for(int j = 0 ; j<=i ; j++){
44                 if(block[i].x < block[j].x && block[i].y < block[j].y){
45                     dp[i] = max(dp[i] , dp[j] + block[i].h);
46                 }
47             }
48         }
49 
50         int maxn = 0;
51         for(int i = 0 ;  i<k ; i++)
52             maxn = max(maxn , dp[i]);
53         printf("Case %d: maximum height = %d
" , ++cas , maxn);
54     }
55     return 0;
56 }

總結

以上是生活随笔為你收集整理的HDU 1069的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。