Submit: 3558 Solved: 2074
[Submit][Status][Discuss]
Description
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上
左下右上右下八个方向上附近的各一个格子，共8个格子。
Input
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
Output
方案数。
Sample Input
3 2
Sample Output
16
HINT
Source
动规 状压DP
f[行][摆放个数][状态]=方案数
仿佛状压以后的背包233
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #define LL long long 8 using namespace std; 9 const int mxn=100010; 10 int t[1<<10],cnt=0; 11 int w[1<<10]; 12 LL f[11][90][1<<10]; 13 int n,k; 14 inline bool check(int p,int r){ 15 if(p&r)return 0; 16 if((p<<1)&r)return 0; 17 if((p>>1)&r)return 0; 18 return 1; 19 } 20 void init(){ 21 int ed=(1<<n)-1;bool flag=0; 22 for(int i=0;i<=ed;i++){ 23 flag=0; 24 for(int j=1;j<n;j++){if(((1<<j)&i) && ((1<<(j-1))&i) ){flag=1;break;}}; 25 if(flag)continue; 26 t[++cnt]=i; 27 for(int j=0;j<n;j++)if(i&(1<<j))w[cnt]++; 28 } 29 return; 30 } 31 int main(){ 32 int i,j,c; 33 scanf("%d%d",&n,&k); 34 init(); 35 f[0][0][0]=1; 36 // int ed=(1<<n)-1; 37 // for(i=1;i<=cnt;i++)printf("%d %d ",t[i],w[i]); 38 for(i=1;i<=cnt;i++)f[1][w[i]][i]=1; 39 for(j=2;j<=n;j++){//行 40 // printf("ck:%d %d :%d %d ",k1,k2,t[k1],t[k2]); 41 for(c=0;c<=k;c++){//摆放个数 42 43 for(int k1=1;k1<=cnt;k1++){ 44 for(int k2=1;k2<=cnt;k2++){ 45 if(w[k2]<=c && check(t[k1],t[k2])) 46 // printf("j:%d c:%d ",j,c); 47 // printf("%lld ",f[j-1][c-w[k2]][k1]); 48 f[j][c][k2]+=f[j-1][c-w[k2]][k1]; 49 // printf("%lld ",f[j][c][k2]); 50 } 51 } 52 } 53 } 54 LL ans=0; 55 for(i=1;i<=cnt;i++)ans+=f[n][k][i]; 56 printf("%lld ",ans); 57 return 0; 58 }