标签：__ 题目 互不侵犯 int NC20240 SCOI2005
题目
- 原题地址：[SCOI2005]互不侵犯
- 题目编号：NC20240
- 题目类型：DP、状压DP
- 时间限制：C/C++ 1秒，其他语言2秒
- 空间限制：C/C++ 262144K，其他语言524288K
1.题目大意
- 在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。
- 国王能攻击到它上下左右，以及左上 左下右上右下八个方向上附近的各一个格子，共8个格子。
2.题目分析
- 学到了新函数：
__builtin_popcount()：统计数字在二进制下1的个数 __builtin_ctz( ) / __buitlin_ctzll( )：返回括号内数的二进制表示形式中末尾0的个数
3.题目代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, K, f[100][2000][100], t;
signed main() {
cin >> n >> K;
for(int i=0;i<(1<<n);i++)if(!(i&(i<<1)))
f[1][i][__builtin_popcount(i)] = 1;
for(int i=2;i<=n+1;i++)for(int j=0;j<(1<<n);j++)for(int k=0;k<(1<<n);k++)
if(!(j&(j<<1))&&!(k&(k<<1))&&!(k&j)&&!(j&(k<<1))&&!(k&(j<<1))){
t = __builtin_popcount(j);
for(int x=0;x+t<=K;x++)
f[i][j][x+t]+=f[i-1][k][x];
}
cout << f[n+1][0][K] << endl;
}
标签：__,
题目,
互不侵犯,
int,
NC20240,
SCOI2005
From： https://www.cnblogs.com/zhangyi101/p/16714926.html