洛谷

洛谷题单指南-状态压缩动态规划-P1896 [SCOI2005] 互不侵犯

原题链接：https://www.luogu.com.cn/problem/P1896

题意解读：求棋盘放m个国王的摆法，国王可以攻击周围8个位置。

解题思路：

可以按行来考虑摆放棋子，用二进制数表示一行的状态，1表示有棋子、0表示无棋子

当前行的状态只受上一行状态的影响，因此可以枚举出所有可能的相邻行的状态转移关系

1、状态表示

设f[i][k][j]表示已摆完第i行，前i行一共有k个国王，且第i行状态是j的方案数。

设cnt[i]表示状态i有多少个国王，也就是二进制中有多少个1。

2、状态转移

枚举所有行 i ：1~n

  枚举所有的国王 k ： 0：m

    枚举所有的合法第i行状态j

      枚举所有合法的第i-1行状态s

        f[i][k][j] += f[i - 1][k - cnt[j]][s]

3、初始化

f[0][0][0] = 1

4、结果

如果只枚举到第n行，则可以将所有f[n][m][]的状态累加；

这里可以多枚举一行到n+1行，这样一来，根据定义，结果即f[n+1][m][0]。

拓展：如果内存受限，还可以通过滚动数组将第一维大小优化为2。

100分代码：

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

const int N = 11, M = N * N;
long long f[N][M][1 << N];
vector<int> states;
vector<int> mp[1 << N];
int cnt[1 << N]; //每种状态有多少个1
int n, m;

int main()
{
    cin >> n >> m;

    //筛出合法行状态
    for(int i = 0; i < 1 << n; i++)
        if(!(i & i >> 1))
            states.push_back(i);

    //筛出合法的行间状态转移
    for(int i : states)
        for(int j : states)
            if(!(i & j) && !((i | j) & (i | j) >> 1))
                mp[i].push_back(j);

    //计算cnt
    for(int i : states)
    {
        int res = 0;
        for(int j = 0; j < n; j++)
            if(i >> j & 1) res++;
        cnt[i] = res;
    }

    f[0][0][0] = 1;
    for(int i = 1; i <= n + 1; i++)
        for(int k = 0; k <= m; k++)
            for(int j : states)
                for(int s : mp[j])
                    if(k - cnt[j] >= 0)
                        f[i][k][j] += f[i - 1][k - cnt[j]][s];

    cout << f[n + 1][m][0];
    return 0;
}