【状态压缩DP】BZOJ1087-[SCOI2005]互不侵犯King
2024-09-27 23:36:48
【题目大意】
在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。
【思路】
先预处理每一行可行的状态(即单行中左右没有相邻的1),存放到usable中。
然后预处理usable中两两之间能否相互转换,存放到map中。
f[i][j][k]第i行,已用去j个国王,当前行状态为usable[k]的情况,四重循环暴力递推即可!
这里用了usable按道理应该会快一些,但是和popoqqq的速度是一样的?不过这个优化应该是有效的!
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=;
const int MAXK=;
const int MAXM=;
int n,m;
int map[MAXN][MAXN];
ll f[MAXM][MAXK][MAXN];//f[i][j][k]第i行,已用去j个国王,当前行状态为k
int usable[MAXN];
int digit[MAXN]; int Usable(int x)
{
if (x<<&x || x>>&x) return ;else return ;
//不能有相邻的1
} int get_digit(int x)
{
int ret=;
while (x) ret+=x&,x>>=;
return ret;
} int Judge(int x,int y)
{
if (x&y || (x<<)&y || (x>>)&y) return ;else return ;
/*不可行的情况有三种*/
} void init()
{
memset(usable,,sizeof(usable));
memset(map,,sizeof(map));
for (int i=;i<<<n;i++)
if (Usable(i)) usable[++usable[]]=i;
/*预处理可行的状态(左右不能有相邻的1)*/
for (int i=;i<=usable[];i++)
for (int j=;j<=usable[];j++)
{
if (Judge(usable[i],usable[j])) map[i][j]=;
}
/*预处理可行的状态中能够转换的状态*/
for (int i=;i<=usable[];i++) digit[i]=get_digit(usable[i]);
/*预处理每一个可行状态中1的个数*/
} ll dp()
{
memset(f,,sizeof(f));
f[][][]=;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
for (int k=;k<=usable[];k++)
if (digit[k]<=j)
{
for (int l=;l<=usable[];l++)
{
if (map[l][k] && digit[l]+digit[k]<=j)
f[i][j][k]+=f[i-][j-digit[k]][l];
}
}
ll ret=;
for (int i=;i<=usable[];i++) ret+=f[n][m][i];
return ret;
} int main()
{
scanf("%d%d",&n,&m);
init();
cout<<dp()<<endl;
return ;
}
最新文章
- svn提交时出现很多乱文件怎么解决
- JavaScript侧边悬浮框
- Oracle数据库BLOB字段的存取
- Android运行异常情况分析(持续更新)
- [LeetCode#201] Bitwise AND of Numbers Range
- document 例子
- 【电视桌面CSWUI】电视桌面(launcher)截图欣赏
- MVC实现SSO
- 方便使用FFMPEG的经验
- JavaScript模板引擎Handlebars
- Spring Websocket实现简易在线聊天功能
- spring MVC 如何接收前台传入的JSON对象数组
- muduo网络库学习笔记(四) 通过eventfd实现的事件通知机制
- Memcache 分布式高可用集群介绍
- Exception in thread Thread-3:第三个线程意外
- Qt4问题集锦
- 如何清理休眠文件(hiberfil.sys)
- 深入Redis 主从复制原理
- MemCache在Windows下环境的搭建及启动
- hdu4352(数位DP + LIS(nlogn))
热门文章
- js 加法运算
- vue双向绑定原理
- C#网络编程基本字段---IPAddress、IPEndPoint
- AtCoder Regular Contest 075 D Widespread
- 1211笔记关于//modal//更改窗口的根控制器//数据存取//Plist属性列表//-“沙盒机制”//plis属性列表//偏好设置//归档普通对象//联系人数据存储//协议与回调函数
- [bzoj3277==bzoj3473]出现k次子串计数——广义后缀自动机+STL
- swift 之嵌套的理解 func chooseStepFunction(backwards: Bool) ->; (Int) ->; Int
- cuda yv12_to_rgb24
- Linux实现利用SSH远程登录服务器详解
- 肢解 HTTP 服务器构建