6
13
2016
0

【UR #10C】【置换群】【动态规划计数】列队

题意:待补充..O_Ob

分析:

20%:枚举所有可能的置换群(排列集合),判断是否满足要求。O(n!^m)

没见过这么难写的暴搜,我真是太年轻。。

伪代码

void dfs(int x)
{
	if(x==m+1){ans++;return;}
	F(i,1,n!){//枚举所有可能为第x个的"元素"
		判断与前面位置的元素是否相容;
		//1:是否满足B矩阵(对于"元素") 
		//2:是否与之前元素相同 
		if(ok) dfs(x+1);
	}
}

代码,关键是用到了next_permutation函数:

//4:35-5:45
const int N=6,M=5;
int n,m,ans;
int T[N],a[M][N],B[M][M];
bool check(int x,int y,int b)
{
	F(i,1,n) T[i]=a[y][a[x][i]];
	F(i,1,n) if(T[i]!=a[b][i]) return false;
	return true;
}
void dfs(int x)
{
	if(x==m+1){ans=(ans+1)%MOD;return;}
	do{
		bool ok=1;
		F(i,1,x) F(j,1,x)//判断1 
			if(B[i][j]<=x && !check(i,j,B[i][j])){ok=0;break;} 
		if(!ok) continue;
		F(i,1,x-1){//判断2 
			bool diff=0;
			F(j,1,n) if(a[i][j]!=a[x][j]) diff=1;//与之前的"排列"是否完全相同. 
			if(!diff){ok=0;break;}
		}
		if(ok) dfs(x+1);
	}while(next_permutation(a[x]+1,a[x]+n+1));//相当于是枚举的过程,不需要写成递归了! 
}
int main()
{
  int tt=read();
  while(tt--){
  	n=read();m=read();ans=0;
  	F(i,1,m) F(j,1,m) B[i][j]=read();
  	F(i,1,m) F(j,1,n) a[i][j]=j;//初始化为最小排列 
	dfs(1);
	printf("%d\n",ans%MOD);
  }
  return 0;
}
Category: 树套树 | Tags: 搜索 STL 动态规划 抽象代数 计数问题 | Read Count: 178

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com