NC20240 [SCOI2005]互不侵犯KING
2022/9/3 6:24:56
本文主要是介绍NC20240 [SCOI2005]互不侵犯KING,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
题目
题目描述
在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。
国王能攻击到它上下左右,以及左上 左下右上右下八个方向上附近的各一个格子,共8个格子。
输入描述
只有一行,包含两个数N,K ( 1 ≤ N ≤ 9, 0 ≤ K ≤ N * N)
输出描述
方案数。
示例1
输入
3 2
输出
16
题解
知识点:状压dp。
状压dp,不过规定要摆 \(k\) 个(这里我用变量 \(t\) 保存),因此要开一个状态表示放了几个。设 \(dp[i][j][k]\) 表示放到第 \(i\) 行,一共放了 \(j\) 个,上一行的状态是 \(k\) 。枚举 \(i,j,k\) 和上一行的上一行状态 \(l\) 。满足 j < num[k] || (k & (k << 1)) == 1
时 \(k\) 不合法,满足 (k & l) || ((k << 1) & l) || ((k >> 1) & l) == 1
时 \(l\) 不合法。有转移方程:
时间复杂度 \(O(nt\cdot 4^n)\)
空间复杂度 \(O(nt\cdot 2^n)\)
代码
#include <bits/stdc++.h> #define ll long long using namespace std; ll dp[15][90][1 << 10]; int num[1 << 10]; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, t; cin >> n >> t; for (int i = 0;i <= (1 << n) - 1;i++) num[i] = __builtin_popcount(i); dp[0][0][0] = 1; for (int i = 1;i <= n;i++) { for (int j = 0;j <= t;j++) { for (int k = 0;k <= (1 << n) - 1;k++) { if (j < num[k] || (k & (k << 1))) continue; for (int l = 0;l <= (1 << n) - 1;l++) { if ((k & l) || ((k << 1) & l) || ((k >> 1) & l)) continue; dp[i][j][k] += dp[i - 1][j - num[k]][l]; } } } } ll ans = 0; for (int i = 0;i <= (1 << n) - 1;i++) ans += dp[n][t][i]; cout << ans << '\n'; return 0; }
这篇关于NC20240 [SCOI2005]互不侵犯KING的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!