洛谷 P1896 [SCOI2005]互不侵犯

题目链接：洛谷 P1896 [SCOI2005]互不侵犯

算法标签: 动态规划（DP）、状态压缩

题目

题目描述

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

注：数据有加强（2018/4/25）

输入格式

只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

输出格式

所得的方案数

输入输出样例

输入 #1

3 2

输出 #1

题解：

状压DP

首先解释为什么是状压DP：

根据题意我们能够得出是通过DP解决
根据题中数据范围\(1 \le N \le 9\)

其次，我们要考虑DP的几个属性：

状态：
1. 我们定义\(f[i][j][s]\)为当前考虑前\(i\)行，第\(i\)行的国王的情况是编号为\(j\)的状态（压缩），在这\(i\)行共有\(s\)个国王的情况的总数。
2. \(sit[]\)和\(gs[]\)分别表示某一点的状态和此状态下这一行放的国王数量。这里需要有dfs预处理。
```
void dfs(int sum, int tot, int now)
{
  if (now >= n)
  {
      sit[ ++ cnt] = sum;
      gs[cnt] = tot;
      return ;
  }
  dfs(sum, tot, now + 1);
  dfs(sum + (1 << now), tot + 1, now + 2);
}
```

转移：

同一行国王的冲突：我们可以直接在预处理时候解决。
上下国王的冲突：if (sit[j] & sit[k]) continue ;
左上方和右下方国王的冲突：if((sit[j] << 1) & sit[k]) continue ;
左下方和右上方国王的冲突：if (sit[j] & (sit[k] << 1)) continue ;
最终的转移过程按照直接处理每一行即可。

for (int i = 2; i <= n; i ++ )
{
  for (int j = 1; j <= cnt; j ++ )
  {
      for (int k = 1; k <= cnt; k ++ )
      {
          if (sit[j] & sit[k])
              continue ;
          if ((sit[j] << 1) & sit[k])
              continue ;
          if (sit[j] & (sit[k] << 1))
              continue ;
          for (int l = gs[j]; l <= m; l ++ )
              f[i][j][l] += f[i - 1][k][l - gs[j]];
      }
  }
}

AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 10;

const int M = 110;

const int NM = 2020;

int n, m, sit[NM], gs[NM], cnt;
long long f[N][NM][M];
void dfs(int sum, int tot, int now)
{
    if (now >= n)
    {
        sit[ ++ cnt] = sum;
        gs[cnt] = tot;
        return ;
    }
    dfs(sum, tot, now + 1);
    dfs(sum + (1 << now), tot + 1, now + 2);
}
int main()
{
    scanf("%d%d", &n, &m);
    dfs(0, 0, 0);
    for (int i = 1; i <= cnt; i ++ )
    {
        f[1][i][gs[i]] = 1;
    }
    for (int i = 2; i <= n; i ++ )
    {
        for (int j = 1; j <= cnt; j ++ )
        {
            for (int k = 1; k <= cnt; k ++ )
            {
                if (sit[j] & sit[k])
                    continue ;
                if ((sit[j] << 1) & sit[k])
                    continue ;
                if (sit[j] & (sit[k] << 1))
                    continue ;
                for (int l = gs[j]; l <= m; l ++ )
                    f[i][j][l] += f[i - 1][k][l - gs[j]];
            }
        }
    }
    long long ans = 0;
    //printf("%d\n", cnt);
    for (int i = 1; i <= cnt; i ++ )
        ans += f[n][i][m];
    printf("%lld\n", ans);
    return 0;
}

国王

洛谷 P1896 [SCOI2005]互不侵犯 - 状压DP