uva437巴比伦塔

巴比伦人有n种长方形方块，每种有无限个，第i种方块的三边边长是xi,yi,zi。对于每一个方块，你可以任意选择一面作为底，这样高就随着确定了。举个例子，同一种方块，可能其中一个是竖着放的，一个是侧着放的，一个是横着放的。

他们想要用堆方块的方式建尽可能高的塔。问题是，只有一个方块的底的两条边严格小于另一个方块的底的两条边，这个方块才能堆在另一个上面。这意味着，一个方块甚至不能堆在一个底的尺寸与它一样的方块的上面。

你的任务是编写一个程序，计算出这个塔可以建出的最高的高度。

【输入】

输入会包含至少一组数据，每组数据的第一行是一个整数n(n<=30)，表示方块的种类数。这组数据接下来的n行，每行有三个整数，表示xi,yi,zi。输入数据会以0结束。

【输出】

对于每组数据，输出一行，其中包含组号(从1开始)和塔最高的高度。按以下格式： Case : maximum height = __

【输入样例】

1

10 20 30

2

6 8 10

5 5 5

7

1 1 1

2 2 2

3 3 3

4 4 4

5 5 5

6 6 6

7 7 7

5

31 41 59

26 53 58

97 93 23

84 62 64

33 83 27

0

【输出样例】

Case 1: maximum height = 40

Case 2: maximum height = 21

Case 3: maximum height = 28

Case 4: maximum height = 342

一道很有意思的DAG最长路

一个长方体需要建三个点表示三种情况，记搜一下就可以了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e6+5;
 4 const int INF=1e9+7;
 5 int x[205],y[205],z[205];
 6 int n,cas,ans,dp[205];
 7 bool g[155][155];
 8 template <class t>void red(t &x)
 9 {
10     x=0;
11     int w=1;
12     char ch=getchar();
13     while(ch<'0'||ch>'9')
14     {
15         if(ch=='-')
16             w=-1;
17         ch=getchar();
18     }
19     while(ch>='0'&&ch<='9')
20     {
21         x=(x<<3)+(x<<1)+ch-'0';
22         ch=getchar();
23     }
24     x*=w;
25 }
26 void input()
27 {
28     freopen("input.txt","r",stdin);
29 }
30 bool check(int a,int b)
31 {
32     if((x[a]<x[b]&&y[a]<y[b])||(x[a]<y[b]&&y[a]<x[b]))
33         return 1;
34     return 0;
35 }
36 int solve(int u)
37 {
38     if(dp[u])
39         return dp[u];
40     dp[u]=z[u];
41     for(int i=0;i<n;++i)
42         if(g[u][i])
43             dp[u]=max(dp[u],solve(i)+z[u]);
44     return dp[u];
45 }
46 int main()
47 {
48     input();
49     while(scanf("%d",&n)==1&&n)
50     {
51         ++cas;
52         ans=0;
53         //memset(g,0,sizeof(g));
54         memset(dp,0,sizeof(dp));
55         printf("Case %d: maximum height = ",cas);
56         for(int i=0;i<n;++i)
57         {
58             red(x[i]);
59             red(y[i]);
60             red(z[i]);
61             x[i+n]=y[i];
62             y[i+n]=z[i];
63             z[i+n]=x[i];
64             x[i+n+n]=z[i];
65             y[i+n+n]=x[i];
66             z[i+n+n]=y[i];
67         }
68         n*=3;
69         for(int i=0;i<n;++i)
70             for(int j=i+1;j<n;++j)
71             {
72                 g[i][j]=check(i,j);
73                 g[j][i]=check(j,i);
74             }
75         for(int i=0;i<n;++i)
76             ans=max(ans,solve(i));
77         printf("%d
",ans);
78     }
79     return 0;
80 }

View Code

uva437巴比伦塔

相关推荐