coreBugZJ

此 blog 已弃。

To Miss Our Children Time, The 36th ACM/ICPC Asia Regional Dalian Site —— Online Contest

To Miss Our Children Time

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65768/65768 K (Java/Others)

Problem Description
Do you remember our children time? When we are children, we are interesting in almost everything around ourselves. A little thing or a simple game will brings us lots of happy time! LLL is a nostalgic boy, now he grows up. In the dead of night, he often misses something, including a simple game which brings him much happy when he was child. Here are the game rules: There lies many blocks on the ground, little LLL wants build "Skyscraper" using these blocks. There are three kinds of blocks signed by an integer d. We describe each block's shape is Cuboid using four integers ai, bi, ci, di. ai, bi are two edges of the block one of them is length the other is width. ci is 
thickness of the block. We know that the ci must be vertical with earth ground. di describe the kind of the block. When di = 0 the block's length and width must be more or equal to the block's length and width which lies under the block. When di = 1 the block's length and width must be more or equal to the block's length which lies under the block and width and the block's area must be more than the block's area which lies under the block. When di = 2 the block length and width must be more than the block's length and width which lies under the block. Here are some blocks. Can you know what's the highest "Skyscraper" can be build using these blocks?
 

Input
The input has many test cases. 
For each test case the first line is a integer n ( 0< n <= 1000) , the number of blocks. 
From the second to the n+1'th lines , each line describing the i‐1'th block's a,b,c,d (1 =< ai,bi,ci <= 10^8 , d = 0 or 1 or 2). 
The input end with n = 0.
 

Output
Output a line contains a integer describing the highest "Skyscraper"'s height using the n blocks.
 

Sample Input
3
10 10 12 0
10 10 12 1
10 10 11 2
2
10 10 11 1
10 10 11 1
0
 

Sample Output
24
11
 


先排序,然后动态规划,dp[ i ] 表示以第 i 个长方体放在顶上的最大高度。
注意长宽相乘使用32位整数会溢出。


 1 #include <iostream>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 typedef  int  I32;
 7 typedef  long long  I64;
 8 
 9 struct Block
10 {
11          I64 a, b, c, d;
12 };
13 
14 bool operator<const Block &a, const Block &b ) {
15         return (  (a.a  < b.a) || 
16                  ((a.a == b.a)&&(a.b  < b.b)) || 
17                  ((a.a == b.a)&&(a.b == b.b)&&(a.d > b.d))
18                );
19 }
20 
21 const I32 N = 1009;
22 
23 I64    dp[ N ];
24 Block  bk[ N ];
25 
26 int main() {
27         I32 n, i, j;
28         I64 ans, t;
29         for ( ; ; ) {
30                 cin >> n;
31                 if ( n < 1 ) {
32                         break;
33                 }
34                 for ( i = 1; i <= n; ++i ) {
35                         cin >> bk[ i ].a >> bk[ i ].b >> bk[ i ].c >> bk[ i ].d;
36                         if ( bk[ i ].a < bk[ i ].b ) {
37                                 t = bk[ i ].a;
38                                 bk[ i ].a = bk[ i ].b;
39                                 bk[ i ].b = t;
40                         }
41                 }
42                 sort( bk+1, bk+n+1 );
43 
44                 for ( i = 1; i <= n; ++i ) {
45                         dp[ i ] = bk[ i ].c;
46                 }
47                 for ( i = 2; i <= n; ++i ) {
48                         switch ( bk[ i ].d ) {
49                         case 0 : 
50                                 for ( j = 1; j < i; ++j ) {
51                                         if ( (bk[j].a<=bk[i].a) && 
52                                              (bk[j].b<=bk[i].b) && 
53                                              (dp[j]+bk[i].c>dp[i]) 
54                                            ) {
55                                                 dp[ i ] = dp[ j ] + bk[ i ].c;
56                                         }
57                                 }
58                                 break;
59                         case 1 : 
60                                 for ( j = 1; j < i; ++j ) {
61                                         if ( (bk[j].a<=bk[i].a) && 
62                                              (bk[j].b<=bk[i].b) && 
63                                              (bk[j].a*bk[j].b < bk[i].a*bk[i].b) && 
64                                              (dp[j]+bk[i].c>dp[i]) 
65                                            ) {
66                                                 dp[ i ] = dp[ j ] + bk[ i ].c;
67                                         }
68                                 }
69                                 break;
70                         case 2 : 
71                                 for ( j = 1; j < i; ++j ) {
72                                         if ( (bk[j].a<bk[i].a) && 
73                                              (bk[j].b<bk[i].b) && 
74                                              (dp[j]+bk[i].c>dp[i]) 
75                                            ) {
76                                                 dp[ i ] = dp[ j ] + bk[ i ].c;
77                                         }
78                                 }
79                                 break;
80                         }
81                 }
82 
83                 ans = dp[ 1 ];
84                 for ( i = 2; i <= n; ++i ) {
85                         if ( ans < dp[ i ] ) {
86                                 ans = dp[ i ];
87                         }
88                 }
89 
90                 cout << ans << endl;
91         }
92         return 0;
93 }
94 

posted on 2011-09-03 18:24 coreBugZJ 阅读(1137) 评论(0)  编辑 收藏 引用 所属分类: ACM


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理