Submit: 5168 Solved: 3006
[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
$f[i][j][k]$表示前$i$行，第$i$行的状态为$j$，放了$k$个的方案
转移的时候枚举上一行的状态是什么
需要预处理出每一个状态的国王数
// luogu-judger-enable-o2 // luogu-judger-enable-o2 #include<cstdio> #define int long long using namespace std; const int MAXN = 10; //#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++) char buf[1<<22],*p1=buf,*p2=buf; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int f[MAXN][1<<MAXN][MAXN*MAXN]; int N, K; int times[1<<MAXN],can[1<<MAXN]; int calc(int x) { int num = 0; for(int i = 0;i < N; i++) if( x & (1 << i) ) num++; return num; } main() { #ifdef WIN32 freopen("a.in","r",stdin); #endif //printf("%d %d %d\n",0<<1,0>>1,0); N = read(), K = read(); int Max = (1 << N) - 1; for(int i = 0;i < Max; i++) times[i] = calc(i), can[i] = (i & (i>>1)) == 0 ? 1 : 0; f[0][0][0] = 1; for(int i = 1;i <= N; i++) for(int j = 0;j < Max; j++) if(can[j]) for(int k = 0;k < Max; k++) if(((j & k) == 0) && ((j & (k << 1)) == 0) && ((j & (k >> 1)) == 0)) for(int l = times[j]; l <= K; l++) f[i][j][l] += f[i-1][k][l - times[j]]; int ans = 0; for(int i = 0;i <= Max; i++) ans += f[N][i][K]; printf("%lld", ans); return 0; }