思路 ：

1)

根据 枚举出每行状态，再筛选出单行之间合法的状态
例： 第i行可能的状态为 0 1 0 1 0 ，或 0 1 1 1 0

显然 根据题意得出 同一行类不能有相邻的 2 个国王
所以在筛选状态时需要判断同行之间是否存在相邻的 2 个一

2)

在处理完单行之间的状态后，先需处理各行之间的状态
0 0 1 0 1 0 1 (i - 1行)
0 0 0 0 0 0 0 (i 行)
0 1 0 1 0 1 0 (i + 1行)
第i行的状态是由 i - 1 行与 i+ 1 行决定的
不难猜测出 第 i 行的状态为 0 ；
但第i + 1行状态也可以由i 和i+ 2 行来决定 所以 我们可以使用 第 i - 1行状态来推出第 i 行状态
用 ** a ** 和 b 来分表表示 第 i - 1 行和 第 i 行的所有状态
得出下列判断条件
(a & b) == 0 && (a | b) 不存在连续的1
可以处理出 由 i - 1行对应的所有状态

#include 
#include using namespace std;const int N = 12, M = 1 << N, K = 110;
typedef long long LL ;vector l1,l2[M];//l1 用来保存第i行的所有合法状态 ;//l2[a]表示a对应的放置集合状态可以转移到的集合状态。int cnt[M];//用来表示每种状态的对应的国王数
LL f[N][M][K];//表示第 i 行 第 m 种状态 k 个国王数 对应的 方案数  
int n,m;bool check(int x)
{for (int i = 0;i < n;i ++ )if(((x >> i) & 1 ) && ((x >> (i + 1)) & 1)) return false; return true;
}int ct(int x)
{int res = 0;for (int i = 0;i < n;i ++ )if((x >> i) & 1) res ++ ;return res;
}int main()
{cin >> n >> m;for (int i = 0;i < 1 << n;i ++ )//枚举出每行状态，再筛选出单行之间合法的状态if(check(i)){l1.push_back(i);cnt[i] = ct(i);}for (int i = 0;i < l1.size();i ++ )for (int j = 0;j < l1.size();j ++ )if((l1[j] & l1[i] ) == 0 && check(l1[j] | l1[i])) l2[i].push_back(j); //存储对应的下标f[0][0][0] = 1;for (int i = 1;i <= n + 1;i ++ )for (int k = 0;k <= m;k ++ )for (int j = 0;j < l1.size();j ++ )for (auto z : l2[j]){int c = cnt[l1[z]];if (c <= k) f[i][j][k] += f[i - 1][z][k - c];//可以由上一层转移到的所有集合的和}cout << f[n + 1][0][m];}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！