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

输入格式
只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)

输出格式
所得的方案数

样例输入
3 2
样例输出
16


首先预处理出一行里面满足题意的情况

判断的时候使用!(x>>1)&x&&!(x<<1)&x

原理自行研究

设所有情况下标为0到max

用pair保存

first代表状态

second代表里面的国王个数(防止重复运算浪费时间)

然后按行进行DP

dp[i][j][j]代表第i行第j种状态里面有l个国王的情况总数

如果满足八个方向不相邻的话

八个方向不相邻的话只需要判断

(y>>1)&x和(y<<1)&x和y&x是不是0

原理自行研究

都不是0就代表可以满足

对应状态转移方程为

\( dp[i][j][l]=\Sigma_{j=0}^{max} dp[i-1][j][l-ans[j].second] \)

最后就只需要对每一个状态求和就可以啦!!

dp[0][0][0]千万不要忘记初始化orz



2019-11-30 19:18 Author: WindCry1

 

分类: DP

0 条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注