NOI P1896 互不侵犯 状压DP
2024-10-21 11:50:11
题目描述
在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。
注:数据有加强(2018/4/25)
输入输出格式
输入格式:
只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)
输出格式:
所得的方案数
输入输出样例
输入样例#1: 复制
3 2
输出样例#1: 复制
16
思路:
这题一看n<=9,二话不说就上状压DP。
f[i][j][k]表示第i行,状态为j,共k个国王时的方案数。
为了减小常数,我们可以先预处理出所有满足要求的状态,存在s数组里,再用sum数组存储当前状态有几个国王。
判断上下是否符合要求也十分简单,乱&一下就可以了,在我的代码中,f[i][j][k]中的j表示第j个状态。
代码:
#include"bits/stdc++.h"
#define db double
#define ll long long
#define vec vector<ll>
#define Mt vector<vec>
#define ci(x) scanf("%d",&x)
#define cd(x) scanf("%lf",&x)
#define cl(x) scanf("%lld",&x)
#define pi(x) printf("%d\n",x)
#define pd(x) printf("%f\n",x)
#define pl(x) printf("%lld\n",x)
//#define rep(i, x, y) for(int i=x;i<=y;i++)
#define rep(i,n) for(int i=0;i<n;i++)
const int N = 1e5+;
const int mod = 1e9 + ;
const int MOD = mod - ;
const int inf = 0x3f3f3f3f;
const db PI = acos(-1.0);
const db eps = 1e-;
using namespace std;
int n,m;
int sum[N];
int s[N];
ll f[][][];
int id=;
int cal(int x){
int ans=;
while(x) ans+=x&,x>>=;
return sum[id]=ans;
}
int main(){
ci(n),ci(m);
int x=(<<n);
for(int i=;i<x;i++) if(!(i&(i<<))) f[][++id][cal(i)]=,s[id]=i;//预处理一行内不冲突的情况
for(int i=;i<=n;i++){
for(int j=;j<=id;j++){
for(int k=;k<=id;k++){
if((s[j]&s[k])||(s[j]&(s[k]>>))||(s[j]&(s[k]<<))) continue;//前后两行不冲突
for(int l=;l+sum[j]<=m;l++) f[i][j][l+sum[j]]+=f[i-][k][l];
}
}
}
ll ans=;
for(int i=;i<=id;i++) ans+=f[n][i][m];//累加
pl(ans);
return ;
}
最新文章
- Tomcat启动失败Unrecognized Windows Sockets error: 0: JVM_Bind
- 装X之写博客
- WPF:常见问题
- Thread-0"; kafka.common.FailedToSendMessageException: Failed to send messages after 3 tries.
- glReadPixels函数
- Python学习之字典详解
- python获取文件的内容
- 越狱Season 1-Episode 10: Sleight of Hand
- ural 1837 Isenbaev&#39;s Number
- 充分利用HTML标签元素 – 简单的xtyle前端框架
- DataGridView的Validating事件注册后删除操作的处理
- extern用法详解
- 银行卡号正则,jq 正则,php正则
- springboot使用Redis,监听Redis键过期的事件设置与使用代码
- 在MFC中支持sqlite3
- day14(2)---列表推导式、生成器推导式、字典推导式、三元表达式
- Day02 (黑客成长日记)
- twindows下omcat8安装后,不能启动服务
- Android 颜色透明度换算
- SolrCloud集群配置
热门文章
- Windows环境下搭建Linux虚拟机
- Eclipse Infrastructure
- Struts2_HelloWorld_3
- CentOS7下SSH服务学习笔记
- Html + JS : 点击对应的按钮,进行选择是隐藏还是显示(用户回复功能)
- 如何用代码的方式取出SAP C4C销售订单创建后所有业务伙伴的数据
- Selenium入门系列1 打开浏览器访问网页,退出浏览器
- 【转载】#437 - Access Interface Members through an Interface Variable
- 转:SSM框架——详细整合教程(Spring+SpringMVC+MyBatis)
- IntelliJ IDEA / Eclipse 自动生成 Author 注释 签名