BZOJ 1087: [SCOI2005]互不侵犯King [状压DP]

时间:2021-12-15 01:58:08

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

3 2

Sample Output

16

orz popoqqq

状压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]的更多相关文章

  1. BZOJ 1087 &lbrack;SCOI2005&rsqb;互不侵犯King ——状压DP

    [题目分析] 沉迷水题,吃枣药丸. [代码] #include <cstdio> #include <cstring> #include <iostream> #i ...

  2. bzoj 1087 &lbrack;SCOI2005&rsqb;互不侵犯King 状态压缩dp

    1087: [SCOI2005]互不侵犯King Time Limit: 10 Sec  Memory Limit: 162 MB[Submit][Status][Discuss] Descripti ...

  3. 【BZOJ1087】 &lbrack;SCOI2005&rsqb;互不侵犯King 状压DP

    经典状压DP. f[i][j][k]=sum(f[i-1][j-cnt[k]][k]); cnt[i]放置情况为i时的国王数量 前I行放置情况为k时国王数量为J #include <iostre ...

  4. &lbrack;BZOJ1087&rsqb; &lbrack;SCOI2005&rsqb; 互不侵犯King &lpar;状压dp&rpar;

    Description 在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案.国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子. Input 只有一行,包 ...

  5. 互不侵犯king &lpar;状压dp&rpar;

    互不侵犯king (状压dp) 在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案.国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子.\(1\le n\ ...

  6. BZOJ-1087 互不侵犯King 状压DP&plus;DFS预处理

    1087: [SCOI2005]互不侵犯King Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2337 Solved: 1366 [Submit][ ...

  7. bzoj1087 互不侵犯King 状压dp&plus;bitset

    题目传送门 题目大意:中文题面. 思路:又是格子,n又只有9,所以肯定是状压dp,很明显上面一行的摆放位置会影响下一行,所以先预处理出怎样的二进制摆放法可以放在上下相邻的两行,这里推荐使用bitset ...

  8. BZOJ 1087 &lbrack;SCOI2005&rsqb;互不侵犯King(状压DP)

    题意:在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案.国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子.n<=9 思路:状压dp,dp[i][ ...

  9. &lbrack;SCOI2005&rsqb;互不侵犯(状压DP)

    嗝~算是状压DP的经典题了~ #\(\mathcal{\color{red}{Description}}\) 在\(N×N\)的棋盘里面放\(K\)个国王,使他们互不攻击,共有多少种摆放方案.国王能攻 ...

随机推荐

  1. python基础(1) 变量类型

    变量赋值: python中的变量不需要类型声明 每个变量在使用前必须赋值,变量赋值以后才会被创建 变量在内存中创建时,包括变量的标识.名称和数据这些信息. EX: #!/usr/bin/python ...

  2. ecplise常用快捷键

    常用 Ctrl+1 快速修复(最经典的快捷键,就不用多说了)Ctrl+D: 删除当前行 Ctrl+Alt+↓ 复制当前行到下一行(复制增加)Ctrl+Alt+↑ 复制当前行到上一行(复制增加)Alt+ ...

  3. CSS中如何让元素隐藏

    在CSS中,让元素隐藏(指屏幕范围内肉眼不可见)的方法很多,有的占据空间,有的不占据空间:有的可以响应点击,有的不能响应点击.下面一个个列出,选一个适合你的 { display: none; /* 不 ...

  4. ubuntu 12&period;04 安装 redis

    原文地址:http://ijonas.com/software-development/nosql/412/ 1 Installing Redis 2.6.x on Ubuntu 12.04 and ...

  5. ActionResult 返回类型

    类名 抽象类 父类 功能 ContentResult     根据内容的类型和编码,数据内容. EmptyResult     空方法. FileResult abstract   写入文件内容,具体 ...

  6. Codeforces Round &num;372 &plus;&num;373 部分题解

    用了两场比赛上Div 1感觉自己好腊鸡的说...以下是这两场比赛的部分题解(不得不说有个黄学长来抱大腿还是非常爽的) Round #372 : Div 2 A:Crazy Computer 题意:给定 ...

  7. Spring mybatis源码篇章-MybatisDAO文件解析&lpar;二&rpar;

    前言:通过阅读源码对实现机制进行了解有利于陶冶情操,承接前文Spring mybatis源码篇章-MybatisDAO文件解析(一) 默认加载mybatis主文件方式 XMLConfigBuilder ...

  8. CacheDependency 的使用方法

    //创建缓存依赖项 CacheDependency dep = new CacheDependency(fileName); //创建缓存 HttpContext.Current.Cache.Inse ...

  9. Kafka特性

    ———————————————————————————————————————————————— [关键原理] 1.消息文件存储(消息堆积能力) 2.消息topic分区 3.消息顺序的保证 4.拉模型 ...

  10. mongodb密码忘了怎么办

    自己电脑上mongodb好长时间没上了,密码竟然给忘了,悲剧啊! 修改auth为false,然后重新启动mongodb 这时候可以不用登陆直接进入 db.changeUserPassword('use ...