【题目大意】

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

最新文章

  1. svn提交时出现很多乱文件怎么解决
  2. JavaScript侧边悬浮框
  3. Oracle数据库BLOB字段的存取
  4. Android运行异常情况分析(持续更新)
  5. [LeetCode#201] Bitwise AND of Numbers Range
  6. document 例子
  7. 【电视桌面CSWUI】电视桌面(launcher)截图欣赏
  8. MVC实现SSO
  9. 方便使用FFMPEG的经验
  10. JavaScript模板引擎Handlebars
  11. Spring Websocket实现简易在线聊天功能
  12. spring MVC 如何接收前台传入的JSON对象数组
  13. muduo网络库学习笔记(四) 通过eventfd实现的事件通知机制
  14. Memcache 分布式高可用集群介绍
  15. Exception in thread Thread-3:第三个线程意外
  16. Qt4问题集锦
  17. 如何清理休眠文件(hiberfil.sys)
  18. 深入Redis 主从复制原理
  19. MemCache在Windows下环境的搭建及启动
  20. hdu4352(数位DP + LIS(nlogn))

热门文章

  1. js 加法运算
  2. vue双向绑定原理
  3. C#网络编程基本字段---IPAddress、IPEndPoint
  4. AtCoder Regular Contest 075 D Widespread
  5. 1211笔记关于//modal//更改窗口的根控制器//数据存取//Plist属性列表//-“沙盒机制”//plis属性列表//偏好设置//归档普通对象//联系人数据存储//协议与回调函数
  6. [bzoj3277==bzoj3473]出现k次子串计数——广义后缀自动机+STL
  7. swift 之嵌套的理解 func chooseStepFunction(backwards: Bool) -&gt; (Int) -&gt; Int
  8. cuda yv12_to_rgb24
  9. Linux实现利用SSH远程登录服务器详解
  10. 肢解 HTTP 服务器构建