BZOJ 1087- [SCOI2005]互不侵犯【状压DP】

快来打我* 2023-10-11 11:57 59阅读 0赞

### 题目描述 ###

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

### 输入格式 ###

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

### 输出格式 ###

所得的方案数，然后

思路：预处理出所有符合条件的状态，即相邻不能有1，然后再判断相邻两行状态是否满足，如果满足的话就转移，最后统计答案就行了，目标状态dp\[n\]\[s\]\[k\] ，其实判断两个状态相同位置不能同时为1，左右相邻也不能同时为1的话用s & p, s & (p << 1)

(s << 1) & p 来判断就可以，而不用像我一样打个表

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    #define ls rt << 1
    #define rs rt << 1|1
    #define mid ((l + r) >> 1)
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    const int maxn = 1e2 + 10;
    const int mod = 1e9;
    int S[maxn], vis[maxn][maxn], num[maxn];
    ll dp[11][maxn][maxn];
    int n, m, tot = 0;
    
    void init()
    {
        for(int i = 0; i < (1 << n); ++i) //预处理出间隔满足的
        {
            int last = -2, flag = 1;
            for(int j = 0; j < n; ++j)
            {
                if(i & (1 << j))
                {
                    if(j - last < 2)
                    {
                        flag = 0;
                        break;
                    }
                    last = j;
                }
            }
            if(flag) S[++tot] = i;
        }
        for(int i = 1; i <= tot; ++i) //预处理判断相邻两行的状态是否合法
        {
            for(int j = 1; j <= tot; ++j)
            {
                bool flag = true;
                for(int k = 0; k < n; ++k)
                {
                    if(((S[i] & (1 << k)) && ((S[j] & (1 << k)) || (S[j] & (1 << (k + 1))))) || ((S[j] & (1 << k)) && (S[i] & (1 << (k + 1)))))
                    {
                        flag = false;
                        break;
                    }
                }
                vis[i][j] = flag;
            }
        }
        for(int i = 1; i <= tot; ++i)
        {
            int cnt = 0;
            for(int j = 0; j < n; ++j)
                if(S[i] & (1 << j))
                    ++cnt;
            num[i] = cnt;
        }
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
        init();
        ll ans = 0;
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= tot; ++i)
            dp[1][i][num[i]] = 1;
        for(int i = 2; i <= n; ++i)
        {
            for(int j = 1; j <= tot; ++j)
            {
                for(int s = 1; s <= tot; ++s)
                {
                    if(vis[j][s])
                    {
                        for(int k = m; k >=num[j]; --k)
                            dp[i][j][k] += dp[i - 1][s][k - num[j]];
                    }
                }
            }
        }
        for(int i = 1; i <= tot; ++i)
            ans += dp[n][i][m];
        printf("%lld\n", ans);
        return 0;
    }