链接:https://www.luogu.org/problemnew/show/P1896
题意:
在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。
思路:
状压dp,dp[i][j][k]。表示。第i行,放j个国王,第j种状态的方法。
预处理第一行,dp。
枚举当前行和上一行的状态。
代码:
#include <iostream> #include <memory.h> #include <string> #include <istream> #include <sstream> #include <vector> #include <stack> #include <algorithm> #include <map> #include <queue> #include <math.h> #include <cstdio> using namespace std; typedef long long LL; const int MAXN = 10; const int STATES = 400; int states[STATES]; int num[STATES]; LL dp[MAXN][MAXN * MAXN][STATES]; int pos = 0; int Get_w(int n) { int res = 0; while (n) { if (n & 1) res++; n >>= 1; } return res; } void Init(int w) { int total = (1 << w); for (int i = 0;i < total;i++) { if ((i & (i << 1)) == 0) { states[++pos] = i; num[i] = Get_w(i); } } } int main() { int n, kk; scanf("%d%d", &n, &kk); Init(n); for (int i = 1;i <= pos;i++) dp[1][num[states[i]]][states[i]] = 1; for (int i = 2;i <= n;i++) { for (int j = 1;j <= pos;j++)//当前行 { for (int k = 1;k <= pos;k++)//上一行 { if (states[j] & states[k] || (states[j] << 1) & states[k] || (states[j] >> 1) & states[k]) continue; for (int x = 0;x <= kk - num[states[j]];x++) dp[i][num[states[j]] + x][states[j]] += dp[i - 1][x][states[k]]; } } } LL res = 0; for (int i = 1;i <= pos;i++) res += dp[n][kk][states[i]]; printf("%lld\n", res); return 0; }