首页 > 代码库 > UVa Problem 10051

UVa Problem 10051

2024-07-08 17:30:48   226人阅读

这题有点类似LIS，由于颜色最多100种，所以只需建立一个100的数组，按对立面的关系以某种颜色为向上面的最大值就可以了。
 
 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 int cube[505][7]; 7 int max_col[105]; 8 int tmp_col[105]; 9 struct{10     int p;11     int wh;12 } pre[505][7];13 14 struct c{15     int p;16     int wh;17 }st_col[105],tmp_st[105];18 int ans,ansc,answ;19 20 int main(){21     int n; int T=0;22     while(scanf("%d",&n),n){23         for(int i=1;i<=100;i++)24         st_col[i].p=st_col[i].wh=-1;25         T++;26         if(T>1) printf("\n");27         ans=answ=ansc=-1;28         memset(max_col,0,sizeof(max_col));29         for(int i=1;i<=n;i++){30             for(int j=1;j<=6;j++)31             scanf("%d",&cube[i][j]);32         }33         for(int i=n;i>=1;i--){34             for(int j=1;j<=6;j++){35                 tmp_col[cube[i][j]]=max_col[cube[i][j]];36                 tmp_st[cube[i][j]]=st_col[cube[i][j]];37             }38             for(int k=1;k<=6;k++){39                 if(k%2){40                     if(tmp_col[cube[i][k]]+1>max_col[cube[i][k+1]]){41                         max_col[cube[i][k+1]]=tmp_col[cube[i][k]]+1;42                         if(ans<max_col[cube[i][k+1]]){43                             ans=max_col[cube[i][k+1]];44                             ansc=i;45                             answ=k+1;46                         }47                         pre[i][k+1].p=tmp_st[cube[i][k]].p;48                         pre[i][k+1].wh=tmp_st[cube[i][k]].wh;49                         st_col[cube[i][k+1]].p=i;50                         st_col[cube[i][k+1]].wh=k+1;51                     }52                 }53                 else{54                     if(tmp_col[cube[i][k]]+1>max_col[cube[i][k-1]]){55                         max_col[cube[i][k-1]]=tmp_col[cube[i][k]]+1;56                         if(ans<max_col[cube[i][k-1]]){57                             ans=max_col[cube[i][k-1]];58                             ansc=i;59                             answ=k-1;60                         }61                         pre[i][k-1].p=tmp_st[cube[i][k]].p;62                         pre[i][k-1].wh=tmp_st[cube[i][k]].wh;63                         st_col[cube[i][k-1]].p=i;64                         st_col[cube[i][k-1]].wh=k-1;65                     }66                 }67             }68         }69         printf("Case #%d\n",T);70         printf("%d\n",ans);71         int p=ansc,pw=answ;72         while(p!=-1){73             printf("%d ",p);74             if(pw==1){75                 printf("front\n");76             }77             if(pw==2) printf("back\n");78             if(pw==3) printf("left\n");79             if(pw==4) printf("right\n");80             if(pw==5) printf("top\n");81             if(pw==6) printf("bottom\n");82             int tp=p,tw=pw;83             p=pre[tp][tw].p;84             pw=pre[tp][tw].wh;85         }86     }87     return 0;88 }
View Code

 


联系
我们