首页 > 代码库 > BZOJ 1087 [SCOI2005]互不侵犯King

BZOJ 1087 [SCOI2005]互不侵犯King

1087: [SCOI2005]互不侵犯King

Description

  在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上 左下右上右下八个方向上附近的各一个格子,共8个格子。

Input

  只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)

Output

  方案数

Sample Input

3 2

Sample Output

16

  很明显这不是一道难题,但此题确实很好地体现状压的普遍套路性。依葫芦画瓢列出状态,再以一种实在的方式列出转移。
  最后说一句,可以预处理出很多东西,速度会快很多。
技术分享
 1  /**************************************************************  2     Problem: 1087  3     User: Doggu  4     Language: C++  5     Result: Accepted  6     Time:724 ms  7     Memory:4884 kb  8 ****************************************************************/ 9   10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13 int n, k, lim; 14 long long f[10][100][520]; 15 inline bool jud(int st,int stb) { 16     int pre=0, bpre=0; 17     while(st||stb) { 18         if((st&1) && (stb&1)) return 0; 19         if((st&1||stb&1) && (pre&1||bpre&1)) return 0; 20         pre=st&1,bpre=stb&1; 21         st>>=1;stb>>=1; 22     } 23     return 1; 24 } 25 inline int cal(int st,int tot=0) {while(st) {if(st&1) tot++;st>>=1;}return tot;} 26 int main() { 27     scanf("%d%d",&n,&k); 28     lim=1<<n; 29     f[0][0][0]=1; 30     for( int i = 1; i <= n; i++ ) for( int j = 0; j <= k; j++ ) for( int st = 0; st < lim; st++ )   31         for( int stb = 0; stb < lim; stb++ ) if(f[i-1][j][stb]&&jud(st,stb)) { 32             f[i][j+cal(st)][st]+=f[i-1][j][stb]; 33         } 34     long long ans = 0; 35     for( int st = 0; st < lim; st++ ) ans+=f[n][k][st]; 36     printf("%lld\n",ans); 37     return 0; 38 } 
状压 4884 kb 724 ms
技术分享
 1 /**************************************************************  2     Problem: 1087  3     User: Doggu  4     Language: C++  5     Result: Accepted  6     Time:40 ms  7     Memory:4892 kb  8 ****************************************************************/ 9   10 #include <cstdio>  11 #include <cstring>  12 #include <algorithm>  13 #include <vector> 14 int n, k, lim, c[520]; 15 std::vector<int> v[520]; 16 long long f[10][100][520];  17 inline bool jud(int st,int stb) {  18     int pre=0, bpre=0;  19     while(st||stb) {  20         if((st&1) && (stb&1)) return 0;  21         if((st&1||stb&1) && (pre&1||bpre&1)) return 0;  22         pre=st&1,bpre=stb&1;  23         st>>=1;stb>>=1;  24     }  25     return 1;  26 }  27 inline int cal(int st,int tot=0) {while(st) {if(st&1) tot++;st>>=1;}return tot;}  28 int main() {  29     scanf("%d%d",&n,&k);  30     lim=1<<n;f[0][0][0]=1; 31     for( int st = 0; st < lim; st++ ) c[st]=cal(st); 32     for( int st = 0; st < lim; st++ ) for( int stb = 0; stb < lim; stb++ ) if(jud(st,stb)) v[st].push_back(stb); 33     for( int i = 1; i <= n; i++ ) for( int j = 0; j <= k; j++ ) for( int st = 0; st < lim; st++ )    34         for( int p = 0; p < v[st].size(); p++ ) if(f[i-1][j][v[st][p]]) f[i][j+c[st]][st]+=f[i-1][j][v[st][p]]; 35     long long ans = 0;  36     for( int st = 0; st < lim; st++ ) ans+=f[n][k][st];  37     printf("%lld\n",ans);  38     return 0;  39 }
状压 4892 kb 40 ms

 

BZOJ 1087 [SCOI2005]互不侵犯King