题目
1087: [SCOI2005]互不侵犯King
Time Limit: 10 Sec Memory Limit: 162 MBDescription
在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。
Input
只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)
Output
方案数。
Sample Input
3 2
Sample Output
16
题解
Orz状态压缩动态规划、、、每行之间是有联系的,所以我们按行来推>_< 我写的时候脑子抽了,行与行之间考虑了关系但是忘记了考虑同一行之间的关系,调了好久,简直不能忍、、、
代码
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 /*Author:WNJXYK*/ 2 #include<cstdio> 3 using namespace std; 4 5 const int MaxB=10; 6 int Pow[MaxB+10]; 7 int FullPow; 8 9 inline void init(int x){ 10 Pow[0]=1; 11 for (int i=1;i<x;i++) Pow[i]=Pow[i-1]<<1; 12 for (int i=0;i<x;i++) FullPow+=Pow[i]; 13 } 14 15 inline int lowbit(int x){ 16 return x&-x; 17 } 18 19 inline int getDigs(int num){ 20 int res=0; 21 while(lowbit(num)!=0){ 22 res++; 23 num-=lowbit(num); 24 } 25 return res; 26 } 27 28 inline bool check(int num){ 29 int l=lowbit(num); 30 num-=l; 31 while(lowbit(num)!=0){ 32 if (lowbit(num)>>1==l) return false; 33 l=lowbit(num);num-=l; 34 } 35 return true; 36 } 37 38 const int Maxs=1<<10; 39 const int Maxn=9; 40 const int Maxk=Maxn*Maxn; 41 long long f[Maxn+5][Maxk+5][Maxs+5]; 42 43 int N,K; 44 int main(){ 45 //freopen("In.txt","w",stdout); 46 scanf("%d%d",&N,&K); 47 init(N); 48 //printf("%d ",getDigs(0)); 49 for (int sta=0;sta<=FullPow;sta++) if (check(sta))f[1][getDigs(sta)][sta]=1; 50 for (int l=2;l<=N;l++){ 51 for (int prev=0;prev<=FullPow;prev++){ 52 for (int nxt=0;nxt<=FullPow;nxt++){ 53 if (!(nxt&prev) && !((nxt<<1)&prev) && !((nxt>>1)&prev) && check(nxt)){ 54 for (int k=getDigs(prev);k<=K;k++){ 55 if (k+getDigs(nxt)<=K){ 56 f[l][k+getDigs(nxt)][nxt]+=f[l-1][k][prev]; 57 } 58 } 59 } 60 } 61 } 62 } 63 /* 64 for (int l=1;l<=N;l++){ 65 for (int sta=0;sta<=FullPow;sta++){ 66 for (int k=1;k<=K;k++){ 67 if (f[l][k][sta]) printf("%d %d %d -> %d ",l,sta,k,f[l][k][sta]); 68 } 69 } 70 } 71 printf(" "); 72 for (int i=0;i<=FullPow;i++)printf("%d %d %d -> %d ",N,i,K,f[N][K][i]);*/ 73 long long Ans=0; 74 for (int sta=0;sta<=FullPow;sta++){ 75 Ans+=f[N][K][sta]; 76 } 77 printf("%lld ",Ans); 78 return 0; 79 }