22软工孟姿好

用户名：dotcpp0669285

访问量：839

签　名：

莫道桑榆晚，为霞尚满天

等　　级
排　　名	841
经　　验	3642
参赛次数	14
文章发表	47
年　　龄	20
在职情况	学生
学　　校	bilibili大学
专　　业	软件工程

　　自我简介：

自强不息

TA的其他文章

旧物有情 # 枚举法求素数
浏览：23

旧物有情 # 枚举法求水仙花数
浏览：14

旧物有情 # 遍历求二维数组转置
浏览：10

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C++代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （Java代码）

状态压缩DP #2495: 信息学奥赛一本通T1592-国王

　　作者: 22软工孟姿好　　　　发表时间：2024-11-20 14:27:03 浏览：8　|　评论：0　

原题链接：信息学奥赛一本通T1592-国王

**大体思路**

如果 n=3，那么 [1 0 0 ] 代表第一行第一个位置放置棋子

由于每一行怎么摆放,只会受到上一行棋子摆放带来的影响

所以我们枚举每一行的所有==合法状态==,来判断后续行

如何判断**行内合法** => 不能有连续的1在一起 即 => `state>>i&1 && state>>i+1&1`

如何判断 **行间合法** => 周围八个格子不能有棋子

当前行为 a 行,上一行为 b 行

首先同一列不能有重复的1 => `a & b == 0`

如何判断两个角? => `a|b` 不能有连续的1即可

`F[N][K][M]` => 前i行放好,且放了K个国王,且当前行状态为M的方案数量

```c++
#define _CRT_SECURE_NO_WARNINGS 1
#include<algorithm>
#include<iostream>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#define MAX 0x3f3f3f3f
#define MIN -0x3f3f3f3f
using namespace std;
typedef long long ll;

const int N = 12, M = 1 << 10, K = 110;
//N行,M列
int n, m;
//用来存储合法状态
vector<int> state;
//用来存储当前合法状态里放了几个国王
int cnt[M];
//用来存储满足了行内合法的数据里谁和谁行间合法,
vector<int> head[M];
//前N行放好,且放置K个国王,且当前行状态为M
//的方案总数
ll f[N][K][M];

//判断行内合法性
bool check(int state) {
	for (int i = 0; i < n; i++) {
		if ((state >> i & 1) && state >> i + 1 & 1)return false;
	}
	return true;
}

//统计当前合法状态的行内合法数据里有多少个1
int count(int state) {
	int res = 0;
	for (int i = 0; i < n; i++)res += state >> i & 1;
	return res;
}

int main() {
	//n行,m列
	cin >> n >> m;

for (int i = 0; i < 1 << n; i++) {
		if (check(i)) {
			state.push_back(i);
			cnt[i] = count(i);
		}
	}
	//在行内合法的数据里找出谁跟谁行间合法
	for (int i = 0; i < state.size(); i ++ ) {
		for (int j = 0; j < state.size(); j++) {
			int a = state[i];
			int b = state[j];
			if((a&b)==0 && check(a|b))head[i].push_back(j);
		}
	}
	//前i行放好,且放了k个国王,并且当前行的状态是M的方案数量
	//F[i][k][m]
	//不放国王也是一种方案
	f[0][0][0] = 1;
	//这里我们多求一行,所以i<=n+1
	//为什么多求一行?
	//如果最后一行我们的状态是00000(就是不放国王) 
	//那么 他就可以完美兼容上一行的所有状态,即相当于进行一个前n行放m个国王的方案数量求和
	for (int i = 1; i <= n + 1; i++) {//行
		for (int j = 0; j <= m; j++) {//放的国王数量
			for (int a = 0; a < state.size(); a++) {//行间合法状态进行计算
				for (int b : head[a]) {//定a,b是跟a合法的状态
					int c = cnt[state[a]];//行内合法数据里有多少个1
					if (j >= c) {//不能超过当前要放的国王数量
						f[i][j][a] += f[i - 1][j - c][b];
					}
				}
			}
		}
	}
	cout << f[n + 1][m][0];
	return 0;
}
```

0.0分

0 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

22软工孟姿好

TA的其他文章

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C++代码）

C二级辅导-等差数列（C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （Java代码）

状态压缩DP #2495: 信息学奥赛一本通T1592-国王

评论区

精彩推荐

A+B for Input-Output Practice （C++代码）

剪刀石头布（C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）from DQM

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

循环入门练习5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

用筛法求之N内的素数。（C语言代码）

复数求和（C语言代码）

22软工孟姿好

TA的其他文章

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C++代码）

C二级辅导-等差数列 （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （Java代码）

状态压缩DP #2495: 信息学奥赛一本通T1592-国王

评论区

精彩推荐

A+B for Input-Output Practice （C++代码）

剪刀石头布 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）from DQM

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

循环入门练习5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

复数求和 （C语言代码）

C二级辅导-等差数列（C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

　　评论区

剪刀石头布（C语言代码）

用筛法求之N内的素数。（C语言代码）

复数求和（C语言代码）