1087: [SCOI2005]互不侵犯King
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 3336 Solved: 1936
[Submit][Status][Discuss]
Description
在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上
左下右上右下八个方向上附近的各一个格子,共8个格子。
Input
只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)
Output
方案数。
Sample Input
Sample Output
状压DP,将每一行的方案二进制压成一维,令f[i][j][k]为第i行用去j个国王状态为k的方案数,然后状态转移如下:
f[i][j][k]=Σf[i-1][j-d[k]][l]
其中l&k=0,l>>1&k=0,l<<1&k=0,d[k]为k的二进制中1的个数
暴力转移即可
记得开long long
预处理来优化
需要判断自身状态可行,判断可行用了移位很巧妙!
//
// main.cpp
// bzoj1087
//
// Created by Candy on 2016/12/24.
// Copyright © 2016年 Candy. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=,M=;
int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
}
int n,m,s;
int g[M][M],can[M],d[M];
ll f[N][N*N][M];
inline int digit(int x){
int re=;
while(x) re+=x&,x>>=;
return re;
}
inline bool check(int x){return !(x<<&x||x>>&x);}
inline bool check(int x,int y){
return !(x&y||x<<&y||x>>&y);
}
int main(int argc, const char * argv[]) {
n=read();m=read();s=<<n;
for(int i=;i<s;i++){
for(int j=i;j<s;j++)g[i][j]=g[j][i]=check(i,j);
d[i]=digit(i);
can[i]=check(i);
}
f[][][]=;
for(int i=;i<=n;i++){
int t=min(m,i*n/+);
for(int j=;j<=t;j++)
for(int k=;k<s;k++) if(can[k]&&d[k]<=j)
for(int l=;l<s;l++) if(can[l]&&g[k][l]&&d[k]+d[l]<=j)
f[i][j][k]+=f[i-][j-d[k]][l];
}
ll ans=;
for(int i=;i<s;i++) ans+=f[n][m][i];
printf("%lld\n",ans);
return ;
}
BZOJ 1087: [SCOI2005]互不侵犯King [状压DP]的更多相关文章
-
BZOJ 1087 [SCOI2005]互不侵犯King ——状压DP
[题目分析] 沉迷水题,吃枣药丸. [代码] #include <cstdio> #include <cstring> #include <iostream> #i ...
-
bzoj 1087 [SCOI2005]互不侵犯King 状态压缩dp
1087: [SCOI2005]互不侵犯King Time Limit: 10 Sec Memory Limit: 162 MB[Submit][Status][Discuss] Descripti ...
-
【BZOJ1087】 [SCOI2005]互不侵犯King 状压DP
经典状压DP. f[i][j][k]=sum(f[i-1][j-cnt[k]][k]); cnt[i]放置情况为i时的国王数量 前I行放置情况为k时国王数量为J #include <iostre ...
-
[BZOJ1087] [SCOI2005] 互不侵犯King (状压dp)
Description 在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案.国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子. Input 只有一行,包 ...
-
互不侵犯king (状压dp)
互不侵犯king (状压dp) 在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案.国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子.\(1\le n\ ...
-
BZOJ-1087 互不侵犯King 状压DP+DFS预处理
1087: [SCOI2005]互不侵犯King Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2337 Solved: 1366 [Submit][ ...
-
bzoj1087 互不侵犯King 状压dp+bitset
题目传送门 题目大意:中文题面. 思路:又是格子,n又只有9,所以肯定是状压dp,很明显上面一行的摆放位置会影响下一行,所以先预处理出怎样的二进制摆放法可以放在上下相邻的两行,这里推荐使用bitset ...
-
BZOJ 1087 [SCOI2005]互不侵犯King(状压DP)
题意:在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案.国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子.n<=9 思路:状压dp,dp[i][ ...
-
[SCOI2005]互不侵犯(状压DP)
嗝~算是状压DP的经典题了~ #\(\mathcal{\color{red}{Description}}\) 在\(N×N\)的棋盘里面放\(K\)个国王,使他们互不攻击,共有多少种摆放方案.国王能攻 ...
随机推荐
-
python基础(1) 变量类型
变量赋值: python中的变量不需要类型声明 每个变量在使用前必须赋值,变量赋值以后才会被创建 变量在内存中创建时,包括变量的标识.名称和数据这些信息. EX: #!/usr/bin/python ...
-
ecplise常用快捷键
常用 Ctrl+1 快速修复(最经典的快捷键,就不用多说了)Ctrl+D: 删除当前行 Ctrl+Alt+↓ 复制当前行到下一行(复制增加)Ctrl+Alt+↑ 复制当前行到上一行(复制增加)Alt+ ...
-
CSS中如何让元素隐藏
在CSS中,让元素隐藏(指屏幕范围内肉眼不可见)的方法很多,有的占据空间,有的不占据空间:有的可以响应点击,有的不能响应点击.下面一个个列出,选一个适合你的 { display: none; /* 不 ...
-
ubuntu 12.04 安装 redis
原文地址:http://ijonas.com/software-development/nosql/412/ 1 Installing Redis 2.6.x on Ubuntu 12.04 and ...
-
ActionResult 返回类型
类名 抽象类 父类 功能 ContentResult 根据内容的类型和编码,数据内容. EmptyResult 空方法. FileResult abstract 写入文件内容,具体 ...
-
Codeforces Round #372 +#373 部分题解
用了两场比赛上Div 1感觉自己好腊鸡的说...以下是这两场比赛的部分题解(不得不说有个黄学长来抱大腿还是非常爽的) Round #372 : Div 2 A:Crazy Computer 题意:给定 ...
-
Spring mybatis源码篇章-MybatisDAO文件解析(二)
前言:通过阅读源码对实现机制进行了解有利于陶冶情操,承接前文Spring mybatis源码篇章-MybatisDAO文件解析(一) 默认加载mybatis主文件方式 XMLConfigBuilder ...
-
CacheDependency 的使用方法
//创建缓存依赖项 CacheDependency dep = new CacheDependency(fileName); //创建缓存 HttpContext.Current.Cache.Inse ...
-
Kafka特性
———————————————————————————————————————————————— [关键原理] 1.消息文件存储(消息堆积能力) 2.消息topic分区 3.消息顺序的保证 4.拉模型 ...
-
mongodb密码忘了怎么办
自己电脑上mongodb好长时间没上了,密码竟然给忘了,悲剧啊! 修改auth为false,然后重新启动mongodb 这时候可以不用登陆直接进入 db.changeUserPassword('use ...