【UVA1352】Colored Cubes
程序员文章站
2022-06-03 18:36:28
...
题面
大火题……上图:
题意
有
n 个正方体(n≤4 ),每个正方体的六个面都有一个颜色。两个正方体是相同的当且仅当其中一个正方体能够通过某种旋转使其六个面的颜色与另一个正方体一一对应。现在你可以对正方体进行重新染色使n 个正方体变成相同的,求染色的最小次数
解法
dfs :
这道题暴搜的关键就是要求出正方体有多少种可能的摆放方案
假设我们以上图的Figure 5为标准方块,可以发现,每一种状态对应【1,6】 的一个全排列,设Figure 5代表的排列为{1,2,3,4,5,6 },然后就可以取手构出其他23种可能的情况(总共24种),例如:将Figure 5右旋一圈得到{5,1,3,4,6,2 }……
得到所以可能的情况之后,我们可以选择1 号方块为标准方块,然后去求其他方块变成1 号方块需要多少次染色,累加取min 即可
复杂度
O(玄学)
代码
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#define Lint long long int
using namespace std;
const int INF=1e9+7;
const int MAXN=50;
const int dice[25][7]={
{ 0,0,0,0,0,0,0 },
{ 0,3,2,6,1,5,4 },{ 0,3,1,2,5,6,4 },{ 0,3,5,1,6,2,4 },{ 0,3,6,5,2,1,4 },
{ 0,5,3,6,1,4,2 },{ 0,6,3,2,5,4,1 },{ 0,2,3,1,6,4,5 },{ 0,1,3,5,2,4,6 },
{ 0,1,2,3,4,5,6 },{ 0,5,1,3,4,6,2 },{ 0,6,5,3,4,2,1 },{ 0,2,6,3,4,1,5 },
{ 0,6,2,4,3,5,1 },{ 0,2,1,4,3,6,5 },{ 0,1,5,4,3,2,6 },{ 0,5,6,4,3,1,2 },
{ 0,2,4,6,1,3,5 },{ 0,1,4,2,5,3,6 },{ 0,5,4,1,6,3,2 },{ 0,6,4,5,2,3,1 },
{ 0,4,5,6,1,2,3 },{ 0,4,6,2,5,1,3 },{ 0,4,2,1,6,5,3 },{ 0,4,1,5,2,6,3 },
};
char name[MAXN][MAXN];
int v[MAXN],c[MAXN];
int s[MAXN][MAXN];
int n,ans,cnt;
int find(char *str)
{
for(int i=1;i<=cnt;i++)
if( !strcmp(name[i],str) ) return i;
strcpy( name[++cnt],str );
return cnt;
}
int cal()
{
int ret=0,tmp;
for(int i=1;i<=6;i++)
{
memset( v,0x0,sizeof v );
tmp=0;
for(int j=1,x;j<=n;j++)
{
x=dice[c[j]][i];
v[s[j][x]]++;
tmp=max( tmp,v[s[j][x]] );
}
ret+=n-tmp;
}
return ret;
}
void dfs(int d)
{
if( d>n ) { ans=min( ans,cal() );return; }
for(c[d]=1;c[d]<=24;c[d]++) dfs( d+1 );
}
int main()
{
char str[MAXN];
while( scanf("%d",&n) && n)
{
ans=6*n,cnt=0;
memset( name,0x0,sizeof name );
memset( c,0x0,sizeof c );
for(int i=1;i<=n;i++)
for(int j=1;j<=6;j++)
{
scanf("%s",str);
int id=find( str );
s[i][j]=id;
}
dfs( 1 );
printf("%d\n",ans);
}
return 0;
}
上一篇: Bellman-Ford算法【模板】
推荐阅读
-
POJ 1642 Stacking Cubes G++ 巧妙 没掌握
-
Codeforces Round #280 (Div. 2)-A. Vanya and Cubes_html/css_WEB-ITnose
-
CodeForces - 1260F Colored Tree(树链剖分 + 组合计数 + 树状数组)
-
【UVA1352】Colored Cubes
-
Codeforces 1398 D. Colored Rectangles(dp)
-
1352 - Colored Cubes (枚举方法)
-
D - Colored Rectangles(动态规划)
-
2015-2016-petrozavodsk-winter-training-camp-spb-su-spb-au-contest F-Colored Path(状压DP)
-
LA 3401 Colored Cubes
-
Codeforces Round #280 (Div. 2)-A. Vanya and Cubes_html/css_WEB-ITnose