首页 > 代码库 > UVa Problem 10051
UVa Problem 10051
这题有点类似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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。