全排列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！种全排列测试正确性

?