Solution of 洛谷-P1896

并不会有更好的阅读体验

\(\text{Sol}\)

我们先看一眼数据范围：

\(1 \le N \le 9\)

没关系，DFS 会出手。

好吧，正经的说，如果暴搜的话复杂度会涨到 \(\text O(2^{n^2})\)，\(\text T\) 到飞起。

此时我们发现有个东西叫状压 \(\text{DP}\) ，也是解决小范围数据的问题。

老套路，枚举每一行，对每一行的每一格是否放置国王进行状态压缩。

然后我们直接枚举每一行的状态与上一行的满足条件的状态进行转移就行了。

此时，其时间复杂度为 \(O(n\cdot (2^{2n}))\)，足以通过此题。

\(\text{Code}\)

#include <bits/stdc++.h>
using namespace std;

int n, k;
long long f[15][1005][100];
int c[1005];

int calc(int i) {
    int res = 0;
    for (int j = 0; j < n; j++)
        res += !!(i & (1 << j));
    return res;
}

bool check2(int i) {
    for (int j = 0; j < n - 1; j++) {
        int a = !!(i & (1 << j));
        int b = !!(i & (1 << (j + 1)));
        if (a and b) return false;
    }
    return true;
}

bool check(int i, int j) {
    int x[15], y[15];
    for (int k = 0; k < n; k++) {
        x[k] = !!(i & (1 << k));
        y[k] = !!(j & (1 << k));
    }
    if (x[0] and (y[0] or y[1])) return false;
    if (x[n - 1] and (y[n - 1] or y[n - 2])) return false;
    for (int k = 1; k < n - 1; k++) {
        if (x[k] and (y[k - 1] or y[k] or y[k + 1]))
            return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;

    for (int i = 0; i < (1 << n); i++)
        f[1][i][calc(i)] = 1;
    for (int i = 0; i < (1 << n); i++)
        c[i] = calc(i);

    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < (1 << n); j++) {
            if (!check2(j)) continue;
            for (int x = c[j]; x <= k; x++) {
                for (int y = 0; y < (1 << n); y++) {
                    if (!check2(y)) continue;
                    if (!check(j, y), !check(y, j)) continue;
                    f[i][j][x] += f[i - 1][y][x - c[j]];
                }
            }
        }
    }

    // for (int i = 1; i <= n; i++) {
    //     for (int j = 0; j < (1 << n); j++) {
    //         for (int x = 0; x <= k; x++) {
    //             cerr << f[i][j][x] << " ";
    //         }
    //         cerr << endl;
    //     }
    //     cerr << endl;
    // }

    long long res = 0;

    for (int i = 0; i < (1 << n); i++)
        res += f[n][i][k];
    cout << res << endl;

    return 0;
}