UVA10051

 1 // 写了挺久的说 = =  谢谢指导我的学长~
 2 // 弄懂之后还是不难的（记性不好啊= = 希望我不要太快忘了才好 ） 
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<algorithm>
 6 #define MAX 3010
 7 using namespace std;
 8 char dir[6][10]={"front", "back", "left", "right", "top" , "bottom"};
 9 struct cube
10 {
11     int weight,top,bot,dir;
12     void init(int w,int t,int b,int d)
13     {
14         weight=w; top=t; bot=b; dir=d;
15     }
16 }a[MAX];
17 int f[MAX],path[MAX];
18 void print(int x)
19 {
20     if(x==-1) return ;
21     print(path[x]);
22     printf("%d %s
",a[x].weight,dir[a[x].dir]);
23 }
24 int main()
25 {
26     int n,cnt=0;
27     int cl[6];
28     while(scanf("%d",&n)!=EOF && n)
29     {
30         int sum=0;
31         for(int i=0;i<n;i++)
32         {
33             for(int j=0;j<6;j++)            
34                 scanf("%d",&cl[j]);        
35             for(int j=0;j<6;j++)
36             {
37                 if(j%2) a[sum++].init(i+1,cl[j],cl[j-1],j);  //记录底面和顶面 
38                 else a[sum++].init(i+1,cl[j],cl[j+1],j);
39             }            
40         }
41         memset(path,-1,sizeof(path));
42         int mx=-1,p=0 ; f[0]=1;
43         for(int i=1;i<sum;i++)
44         {
45             f[i]=1;
46             for(int j=0;j<i;j++)
47             {
48                 if(a[i].weight > a[j].weight && a[i].top == a[j].bot && f[j]+1>f[i] )  // LIS 
49                 {
50                     f[i]=f[j]+1;
51                     path[i]=j;
52                     if(f[i]>mx) mx=f[i],p=i;
53                 }
54             }
55         }
56         if(cnt) printf("
"); 
57         printf("Case #%d
%d
",++cnt,mx);
58         print(p);        
59     }
60     return 0;
61 }