全排列DP计数---zoj_1217

       题目中需要对0-8九个数的全排列计数（字典序），来完成一张对于的HASH表，显然状态空间中共有9！个状态，可以看成一颗树，第一层9个子节点，第二层每个节点8个子节点，第三层每个节点7个子节点，以此类推。

       那么对于某中特定的排列，要求它的字典计数，只需求出每一层在该点之后的节点个数乘以该层对应的DP项。。。

     

int dp[10]={1,1,2,6,24,120,720,5040,40320,362880};
int getHash(int code[9])
{
	int sum=0;
	bool flag[9];
	int k;
	memset(flag,false,sizeof(flag));
	for(int i=0;i<9;++i)
	{
		k=0;
		for(int j=code[i]+1;j<9;++j)
		{
			if(!flag[j])
				++k;
		}
		sum+=k*dp[8-i];
		flag[code[i]]=true;
	}
	return 362879-sum;
}
void test(bool flag[9],int b,int num[9])
{
	if(b>8)
	{
		printf("%d\n",getHash(num));
		return;
	}
	for(int i=0;i<9;++i)
	{
		if(!flag[i])
		{
			flag[i]=true;
			num[b]=i;
			test(flag,b+1,num);
			flag[i]=false;
		}
	}
}
int main()
{
	bool ff[9];
	int nn[9];
	memset(ff,false,sizeof(ff));
	memset(nn,false,sizeof(nn));
	test(ff,0,nn);
	int a[9]={0,1,2,3,4,5,6,7,8};
	int b[9]={8,7,6,5,4,3,2,1,0};
	printf("%d\n",getHash(b));
}

 代码中test函数枚举所有9！种全排列测试正确性