题目描述 Description 在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
输入描述 Input Description 只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
输出描述 Output Description 方案数。
样例输入 Sample Input 3 2
样例输出 Sample Output 16
数据范围及提示 Data Size & Hint 1 <=N <=9, 0 <= K <= N * N
题解 本题看起来和八皇后很类似，但实际上用搜索会T掉，正确的解法是状压dp。 阶段：用行来划分阶段，每一行n个位置放国王记为1，不放记为0，一行用一个longlong进行状态压缩，每行状态数不会超过。如此划分阶段，转移时即可只考虑上一行和这一行。 然后可以预处理出所有合法的状态： 先对每一行，从小到大枚举状态i，若i and (i shr 1)为0则说明状态i没有出现国王在一行中相邻的情况，i合法，记录之，并记下i对应的国王数cnt[i]； 再对相邻的两行，从小到大枚举状态i，j，若i和j均合法则判断[i and j],[i and (j shr 1)], [j and (i shr 1)]，若三者均为0说明状态i和j没有出现国王在列上相邻或在对角线上相邻的情况，合法，记录之。 状态：记f[p][k][i]为前p行共放了k个国王且第p行的状态为i的方案数。 转移：枚举行数p(从2开始)，上一行的状态i和这一行的状态j，，若i合法、j合法且i和j的组合合法，枚举决策k,k表示前i行放的国王数， 初始化：第一行，枚举状态i，若i合法，f[1][cnt[i]][i]=1，否则为0。 答案： 时间复杂度：，这是上限，一般达不到 空间复杂度：，足够了
Code
;const int maxn = 9;int n, m, cnt[1 << maxn];ll f[maxn + 1][65][1 << maxn], ans, tot;bool sline[1 << maxn], dline[1 << maxn][1 << maxn];void read(int &a){int f = 1;char ch = getchar();a = 0;while(ch < ‘0’ || ch > ‘9’){if(ch == ‘-‘) f = -1;ch = getchar();}while(ch >= ‘0’ && ch <= ‘9’){a = a*10 + ch – 48;ch = getchar();}a *= f;}void write(ll a){int top = 0;char ch[maxn << 2];if(a < 0){putchar(‘-‘);a = -a;}do {ch[top++] = a%10 + 48;a /= 10;} while(a);while(top–) putchar(ch[top]);putchar(‘\n’);}void init(){read(n); read(m);tot = (1 << n) – 1;for(int i = 0; i <= tot; ++i) if(((i >> 1) & i) == 0){for(int j = i; j > 0; j >>= 1) cnt[i] += (j & 1);sline[i] = true;}for(int i = 0; i <= tot; ++i) if(sline[i])for(int j = 0; j <= tot; ++j) if(sline[j])if((i & j) == 0 && ((i >> 1) & j) == 0 && ((j >> 1) & i) == 0)dline[i][j] = true;for(int i = 0; i <= tot; ++i) if(sline[i]) f[1][cnt[i]][i] = 1;}void work(){for(int p = 2; p <= n; ++p)for(int i = 0; i <= tot; ++i) if(sline[i])for(int j = 0; j <= tot; ++j) if(sline[j])if(dline[i][j])for(int k = cnt[i]; k + cnt[j] <= m; ++k)f[p][k + cnt[j]][j] += f[p – 1][k][i];for(int i = 0; i <= tot; ++i) ans += f[n][m][i];write(ans);}int main(){init();work();return 0;}
没有什么可留恋，只有抑制不住的梦想，
