题目描述
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
注：数据有加强（2018/4/25）
输入输出格式
输入格式：
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
输出格式：
所得的方案数
输入输出样例
输入样例#1： 复制
3 2
输出样例#1： 复制
16
/* 状压DP的经典题。 转移为f[i][j][s] = sum(f[i-1][k][s-tot(i)]) 其中i表示现在是第i行 j表示第i行国王的状态 s表示包括第i行在内总共用的国王数 */ #include <bits/stdc++.h> using namespace std; long long dp[15][1000][100]; int cnt = 0,n,k,c[1<<10],s[1<<10]; void dfs(int cond,int sum,int pos){ if(pos > n){//出了边界，说明这一行枚举到头了 c[++cnt] = cond;//处理cnt+1这一种情况的状态 s[cnt] = sum;//计算cnt这一种情况的国王数 return ;//直接返回 } dfs(cond+(1<<pos-1),sum+1,pos+2);//在这一点放国王的情况 pos+2是因为pos这里放了国王的话，pos+1一定会被攻击到 dfs(cond,sum,pos+1);//不在这一点放国王的情况 继续搜索下一个点 } int main() { scanf("%d%d",&n,&k); dfs(0,0,1);//预处理出一行的状态 for(int i = 1;i <= cnt;i++) dp[1][c[i]][s[i]] = 1;//处理第一行 for(int i = 2;i <= n;i++)//从第二行开始 for(int j = 1;j <= cnt;j++)//枚举这行的所有状态 for(int h = 1;h <= cnt;h++){//枚举上一行的所有状态 if(c[j] & c[h]) continue;//上下重复 if((c[j] << 1) & c[h]) continue;//左上右下重复 if((c[j] >> 1) & c[h]) continue;//右上左下重复 for(int sum = k;sum >= s[j];sum--)//枚举这一行除外的行用的国王数量 dp[i][c[j]][sum] = dp[i][c[j]][sum] + dp[i-1][c[h]][sum-s[j]]; } long long ans = 0; for(int i = 1;i <= cnt;i++) ans += dp[n][c[i]][k];//枚举最后一行所有状态，累加 printf("%lld",ans); return 0; }