题目#

[SCOI2005] 互不侵犯#

题目描述#

在 $N \times N$ 的棋盘里面放 $K$ 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。对于全部数据， $1 \le N \le 9$ ， $0 \le K \le N\times N$ 。

题解#

设f[i][j][k]表示推到了第i行，到目前为止选了j个国王，第i行的状态为k的方案数

然后枚举i,j,k以及前一行的状态转移即可

问题#

1.不开long long见祖宗

2.第二位要开N * N！

代码#

1
#include<bits/stdc++.h>
2
#define int long long
3
using namespace std;
4

5
int read()
6
{
7
  int f = 1, x = 0;
8
  char ch = getchar();
9
  while(ch < '0' || ch > '9')
10
  {
11
    if(ch == '-') f = -1;
12
    ch = getchar();
13
  }
14

15
  while(ch >= '0' && ch <= '9')
16
  {
17
    x = x * 10 + ch - '0';
18
    ch = getchar();
19
  }
20
  return f * x;
21
}
22
const int N = 10;
23
int f[N][N * N][1 << 9];
24
int sum[1 << 9];
25
int n, k;
26

27
int getsum(int x)
28
{
29
  int ans = 0;
30
  while(x)
31
  {
32
    x &= (x - 1);
33
    ans++;
34
  }
35
  return ans;
36
}
37

38
signed main()
39
{
40
  for(int i = 0;i < (1 << 9);i++)
41
  {
42
    sum[i] = getsum(i);
43
  }
44
  n = read(), k = read();
45
  for(int s = 0;s < (1 << n);s++)
46
  {
47
    f[1][sum[s]][s] = 1;
48
  }
49

50
  for(int i = 2;i <= n;i++)
51
  {
52
    for(int j = 0;j <= k;j++)
53
    {
54
      for(int s = 0;s < (1 << n);s++)
55
      {
56
        if((s >> 1) & s || (s << 1) & s || sum[s] > j) continue;
57
        for(int fl = 0;fl < (1 << n);fl++)
58
        {
59
          if((fl >> 1) & fl || (fl << 1) & fl || (fl << 1) & s || fl & s || (fl >> 1) & s || sum[fl] + sum[s] > j) continue;
60
          f[i][j][s] += f[i - 1][j - sum[s]][fl];
61
        }
62
      }
63
    }
64

65
  }
66

67
  long long ans = 0;
68
  for(int s = 0; s < (1 << n);s++)
69
  {
70
    if((s >> 1) & s) continue;
71
      ans += f[n][k][s];
72
  }
73
  cout << ans;
74
  return 0;
75
}