P1896 互不侵犯

题目名称

问题

P1896 互不侵犯
在 $N \times N$ 的棋盘里放 $K$ 个国王，每个国王只能攻击它周围八格。问总共有多少种方案。
数据规模：$N \le 9, K \le N \times N$。

最直接的观察 $N \le 9$，又是一个方案数统计问题，所以我们可以考虑状态压缩 DP来计数。

注意到只有相邻两行之间的状态会相互影响，所以我没可以考虑按行切分阶段，把每一行的状态压缩成一个二进制状态。

接下来考虑状态转移，由于每个国王相邻的八个不允许存在国王，对于当前行，我们可以直接用 ( mask & ( mask << 1 ) ) == 0 来判断。对于相邻行，我们可以通过下列代码来判断：

bool check( int pre, int cur ) {
	if( cur & cur ) return 0;
	if( ( pre << 1 ) & cur ) return 0;
	if( ( pre >> 1 ) & cur ) return 0;
	return 1;
}

OK，接下来我们考虑具体的状态定义，记 $f[i][k][cur]$ 表示处理完前 $i$ 行，总共放置了 $k$ 个国王，第 $i$ 行状态为cur 的方案数。

转移，在 pre 和 cur 相容的情况下：$f[i][k + popcount(cur)][cur] += f[i-1][k][pre]$。

最后考虑初始化，初始的条件，由于是方案计数类问题，我们记 $f[0][0][0] = 1$，表示存在一种空方案用于转移。

这类状态压缩的 mask 只记录了当前行的状态，能够按行 DP，是因为国王只会攻击相邻行，所以我们不需要再保留上一行的状态。

摘要

这类轮廓状压的关键：找出会继续影响未来决策的最后一层边界，保存转移所需的最小信息即可。

代码

▶

P1896

ll dp[10][205][1030];

bool check( ll x, ll y ) {
    if( x & y ) return 0;
    if( (x >> 1) & y ) return 0;
    if( (x << 1) & y ) return 0;
    return 1;
}

void solve( ) {
    int n = read( ), k = read( );

    dp[0][0][0] = 1;

    for( int i = 1; i <= n; ++ i ) {
        for( int j = 0; j <= k; ++ j ) {
            for( int cur = 0; cur < (1 << n); ++ cur ) {
                int cnt = __builtin_popcount( cur );
                if( cnt > j ) continue;
                if( (cur << 1) & cur ) continue;
                for( int pre = 0; pre < (1 << n); ++ pre ) {
                    if( check( cur, pre ) ) dp[i][j][cur] += dp[i-1][j-cnt][pre];
                }
            }
        }
    }

    ll ans = 0;
    for( int mask = 0; mask < (1 << n); ++ mask ) ans += dp[n][k][mask];
    cout << ans << '\n';
}