因為資料量非常小(n<=10)，是以可以用dfs枚舉每個長方體的狀态，然後求LIS。
1 #include <algorithm>
2 #include <iostream>
3 #include <cstring>
4 #include <cstdio>
5 using namespace std;
6
7 const int N = 10;
8 int dp[N];
9 int n, ans;
10
11 struct T
12 {
13 int a, b, c;
14 } t[N];
15
16 struct X
17 {
18 int a, b;
19 } x[N], tmp[N];
20
21 bool cmp( X p, X q )
22 {
23 if ( p.a != q.a ) return p.a < q.a;
24 return p.b < q.b;
25 }
26
27 void dfs( int cur )
28 {
29 if ( cur == n )
30 {
31 for ( int i = 0; i < n; i++ )
32 {
33 tmp[i] = x[i];
34 if ( tmp[i].a > tmp[i].b )
35 {
36 swap( tmp[i].a, tmp[i].b );
37 }
38 }
39 sort( tmp, tmp + n, cmp );
40 for ( int i = 0; i < n; i++ )
41 {
42 dp[i] = 1;
43 for ( int j = 0; j < i; j++ )
44 {
45 if ( tmp[j].b <= tmp[i].b )
46 {
47 dp[i] = max( dp[i], dp[j] + 1 );
48 }
49 }
50 ans = max( ans, dp[i] );
51 }
52 return ;
53 }
54 x[cur].a = t[cur].a;
55 x[cur].b = t[cur].b;
56 dfs( cur + 1 );
57 x[cur].a = t[cur].a;
58 x[cur].b = t[cur].c;
59 dfs( cur + 1 );
60 x[cur].a = t[cur].b;
61 x[cur].b = t[cur].c;
62 dfs( cur + 1 );
63 }
64
65 int main ()
66 {
67 int _case = 1;
68 while ( scanf("%d", &n), n )
69 {
70 for ( int i = 0; i < n; i++ )
71 {
72 scanf("%d%d%d", &t[i].a, &t[i].b, &t[i].c);
73 }
74 ans = -999;
75 dfs(0);
76 printf("Case %d: %d\n", _case++, ans);
77 }
78 return 0;
79 } 轉載于:https://www.cnblogs.com/huoxiayu/p/4732934.html