题目描述

在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 ;
}

最新文章

  1. Tomcat启动失败Unrecognized Windows Sockets error: 0: JVM_Bind
  2. 装X之写博客
  3. WPF:常见问题
  4. Thread-0&quot; kafka.common.FailedToSendMessageException: Failed to send messages after 3 tries.
  5. glReadPixels函数
  6. Python学习之字典详解
  7. python获取文件的内容
  8. 越狱Season 1-Episode 10: Sleight of Hand
  9. ural 1837 Isenbaev&#39;s Number
  10. 充分利用HTML标签元素 – 简单的xtyle前端框架
  11. DataGridView的Validating事件注册后删除操作的处理
  12. extern用法详解
  13. 银行卡号正则,jq 正则,php正则
  14. springboot使用Redis,监听Redis键过期的事件设置与使用代码
  15. 在MFC中支持sqlite3
  16. day14(2)---列表推导式、生成器推导式、字典推导式、三元表达式
  17. Day02 (黑客成长日记)
  18. twindows下omcat8安装后,不能启动服务
  19. Android 颜色透明度换算
  20. SolrCloud集群配置

热门文章

  1. Windows环境下搭建Linux虚拟机
  2. Eclipse Infrastructure
  3. Struts2_HelloWorld_3
  4. CentOS7下SSH服务学习笔记
  5. Html + JS : 点击对应的按钮,进行选择是隐藏还是显示(用户回复功能)
  6. 如何用代码的方式取出SAP C4C销售订单创建后所有业务伙伴的数据
  7. Selenium入门系列1 打开浏览器访问网页,退出浏览器
  8. 【转载】#437 - Access Interface Members through an Interface Variable
  9. 转:SSM框架——详细整合教程(Spring+SpringMVC+MyBatis)
  10. IntelliJ IDEA / Eclipse 自动生成 Author 注释 签名