Leo 搭积木

Leo 搭积木
【问题描述】
Leo是一个快乐的火星人，总是能和地球上的 OIers玩得很 high。
2012 到了， Leo 又被召回火星了，在火星上没人陪他玩了，但是
他有好多好多积木，于是他开始搭积木玩。
火星人能制造 n 种积木，积木能无限供应。每种积木都是长方体，
第 i 种积木的长、宽、高分别为 li、 wi、 hi。积木可以旋转，使得
长宽高任意变换。 Leo 想要用这些积木搭一个最高的塔。问题是，如
果要把一个积木放在另一个积木上面，必须保证上面积木的长和宽都
严格小于下面积木的长和宽。这意味着，即使两块长宽相同的积木也
不能堆起来。
火星上没有电脑，好心的你决定帮助 Leo 求出最高的塔的高度。
【输入说明】
第一行，一个整数 n，表示积木的种数
接下来 n 行，每行 3 个整数 li， wi， hi，表示积木的长宽高
【输出说明】
一行一个整数，表示塔高的最大值
【提示】
每种积木都可以拆分成高度分别为 li、 wi、 hi 的三种积木，另

两边作为长和宽，保证长>=宽。

输入

1
10 20 30

输出

输入

2
6 8 10
5 5 5

输出

输入

5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27

输出

342

对于此题,将所有可能的积木全部存储起来,然后以长为第一关键字,宽为第二关键字排序(从大到小),再dp一道就行了.

我有两组超时,如果有人能有更好的算法可以跟我说.

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <fstream>
 5 /* run this program using the console pauser or add your own getch, system("pause") or input loop */
 6 using namespace std;
 7 
 8 ifstream fin("brick.in");
 9 ofstream fout("brick.out");
10 
11 int cnt_block=0;
12 struct id{
13  int chang;    
14  int kuan;
15  int gao;    
16 };
17 id block[9005]={0};
18 int jiyi[9005][9005];
19 
20 bool qqsort(id a,id b);
21 int dp(int now,int pan);
22 
23 
24 bool qqsort(id a,id b){
25 //if(a.chang>b.chang&&a.kuan>b.kuan)return 1;    
26 if(a.chang>b.chang)return 1;
27 if(a.chang==b.chang&&a.kuan>b.kuan)return 1;
28 return 0;    
29 }
30 
31 
32 int dp(int now,int pan){
33 if(now>cnt_block*3)return 0;
34 if(jiyi[now][pan]!=-1)return jiyi[now][pan];    
35 int yao=0,unyao=0;    
36 if((block[now].chang<block[pan].chang&&block[now].kuan<block[pan].kuan)||pan==0)
37  yao=block[now].gao+dp(now+1,now);    
38 unyao=dp(now+1,pan);    
39 if(yao>unyao)unyao=yao;
40 jiyi[now][pan]=unyao;
41 return unyao;
42     
43 }
44 
45 
46 int main(int argc, char** argv) {
47 fin>>cnt_block;
48 int cnt_blocks=0;
49 for(int x=1;x<=cnt_block;x++){
50 int a,b,c;
51 fin>>a>>b>>c;     
52 block[++cnt_blocks].chang=max(a,b);
53 block[cnt_blocks].kuan=min(a,b);
54 block[cnt_blocks].gao=c;
55 block[++cnt_blocks].chang=max(a,c);
56 block[cnt_blocks].kuan=min(a,c);
57 block[cnt_blocks].gao=b;
58 block[++cnt_blocks].chang=max(b,c);
59 block[cnt_blocks].kuan=min(b,c);
60 block[cnt_blocks].gao=a;    
61 }
62 sort(block+1,block+1+cnt_blocks,qqsort);
63 //for(int x=1;x<=cnt_blocks;x++){
64 // cout<<block[x].chang<<" "<<block[x].kuan<<" "<<block[x].gao<<endl;
65 //}
66 memset(jiyi,-1,sizeof(jiyi));
67 int ans=dp(1,0);
68 cout<<ans;
69 fout<<ans;
70 return 0;
71 }