SCOI2051 互不侵犯

原题链接:https://www.luogu.org/problem/P1896

收录于 NOI 系列题解集


思路

一道简单的状压 DP 模板题。

类似于八皇后问题,但是由于国王只能控制周边一格,暴力 DFS 显然会TLE。观察数据范围,考虑状压 DP。

先预处理出单行可能状态,及每个单行可能状态所使用的国王数。

利用位运算,保证状态转移后的情形下,国王之间互不侵犯。

状态转移方程

dp(n, k, s) = \sum dp(n-1, l, t)

dp(n, k, s) 表示棋盘前 n 行共有 k 个国王,且第 n 行的状态为 s 的总方案数。

其中 l 表示前 n-1 行的国王总数 ,t 表示上一行的可能状态。

求和时,t 取单行的所有可能状态,且 st 需满足一定条件,保证国王之间互不侵犯。

s & t(s << 1) & ts & (t << 1)任一不为0时,条件不满足。

那么,答案为 \sum dp(N, K, s)

其中,s 取单行的所有可能状态。

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#define min(a, b) ((a) > (b) ? (b) : (a))

const int MAXN = 10, MAXK = 81, MAXS = 1024;
int N, K, can[MAXS], cnt[MAXS], sz;
long long dp[MAXN][MAXK][MAXS], ans;

void dfs(int k, int n, int s) {
  if (n >= N) {
    can[sz] = s;
    cnt[sz] = k;
    ++sz;
    return;
  }
  dfs(k, n + 1, s);
  dfs(k + 1, n + 2, (1 << n) | s);
}

int main() {
  scanf("%d%d", &N, &K);
  sz = 0;
  dfs(0, 0, 0);
  for (int i = 0; i < sz; ++i) {
    dp[1][cnt[i]][can[i]] = 1;
  }
  for (int n = 2; n <= N; ++n) {
    for (int i = 0; i < sz; ++i) {
      for (int j = 0; j < sz; ++j) {
        if (can[i] & can[j]) continue;
        if ((can[i] << 1) & can[j]) continue;
        if (can[i] & (can[j] << 1)) continue;
        for (int k = K; k >= cnt[j]; --k) {
          dp[n][k][can[j]] += dp[n - 1][k - cnt[j]][can[i]];
        }
      }
    }
  }
  ans = 0;
  for (int i = 0; i < sz; ++i) ans += dp[N][K][can[i]];
  printf("%lld\n", ans);
  return 0;
}
点赞

Leave a Reply