题解【洛谷P1896】[SCOI2005]互不侵犯

棋盘类状压 DP 经典题。

我们考虑设 \(dp_{i,j,s}\) 表示前 \(i\) 行已经摆了 \(j\) 个国王，且第 \(i\) 行国王摆放的状态为 \(s\) 的合法方案数。

转移的时候枚举每一行的每种状态及已经摆放了的国王数量，然后枚举上一行的状态，如果合法就更新。

但是这样做的时间复杂度大致是 \(10 \times 10^2 \times 2^{10} \times 10^3 = 10^9\) 的，明显会 TLE，于是我们考虑如何优化。

其实我们在转移时有很多不合法的状态，即转移时的无用状态。于是我们考虑预处理一下所有在转移时合法的状态，这样优化后我们就可以 AC 本题了。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 13, maxm = 1 << 11, maxk = 103;

int n, m, k;

int cnt[maxm]; //存储每个状态中 1 的个数

long long ans, dp[maxn][maxk][maxm];

vector <int> g; //存储合法的状态

vector <int> can[maxm]; //存储每个状态可以转移到的合法状态

//判断一个状态是否合法，即判断是否有连续的 2 个 1

inline bool check(int x)

{

    for (int i = 0; i < n; i+=1)

        if ((x >> i & 1) && (x >> (i + 1) & 1))

            return false;

    return true;

}

//求一个状态中 1 的个数

inline int get_1(int x)

{

    int sum = 0;

    for (int i = 0; i < n; i+=1)

        if (x >> i & 1)

            ++sum;

    return sum;

}

int main()

{

    cin >> n >> m;

    for (int i = 0; i < (1 << n); i+=1) //枚举所有状态

        if (check(i)) //该状态合法

        {

            g.push_back(i);

            cnt[i] = get_1(i);

        }

    int len = g.size(); //合法状态的个数

    for (int i = 0; i < len; i+=1)

        for (int j = 0; j < len; j+=1) //枚举每两个合法的状态

        {

            int a = g[i], b = g[j];

            if (!(a & b) && check(a | b))

                can[i].push_back(j); //两个状态在转移时可以放相邻两行

        }

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

    for (int i = 1; i <= n; i+=1) //枚举行数

        for (int j = 0; j <= m; j+=1) //枚举国王个数

            for (int k = 0; k < len; k+=1) //枚举状态

            {

                int len1 = can[k].size(), geshu_1 = cnt[g[k]];

                for (int ll = 0; ll < len1; ll+=1) //枚举上一行的状态

                {

                    int l = g[can[k][ll]];

                    if (j >= geshu_1) //可以进行转移

                        dp[i][j][g[k]] += dp[i - 1][j - geshu_1][l];

                }

            }

    for (int i = 0; i < (1 << n); i+=1) //枚举最后一行的状态

        ans += dp[n][m][i]; //统计答案

    cout << ans << endl; //输出答案

    return 0;

}

巴特西

题解【洛谷P1896】[SCOI2005]互不侵犯

最新文章

热门文章