当前位置:首页 > 动态规划 > 状压DP > 正文
SSOJ2157猛兽军团1
2353+

题目大意:猛兽会攻击自身周围8个格子,请问N*N的方阵放入K只猛兽,共有多少种可行方案?

【题目描述】

修罗王准备将他的猛兽军团放置在N×N的方阵中,但是猛兽们均有自己的地盘,它们会攻击自身周围八个格子的任何目标,现猛兽有K只,要求猛兽之间不能互相攻击,问有多少种可行方案?

【输入格式】

两个整数N(1≤N≤10)和K(0≤K≤N²)

【输出格式】

可行放置方案个数

【样例输入1】

3 2

【样例输出1】

16

【样例输入2】

4 4

【样例输出2】

79

解题思路

一行看成一个状态,0表示不放猛兽,1表示放猛兽,5=101表示该行从右数第1、3列放猛兽,f[i][j][k]表示前面i行放k个猛兽,且第i行状态是j的方案数。

预处理:首先是可行状态s,同一行放猛兽,猛兽不能相邻,即j&j<<1为0,预处理可行状态到s数组;其次是状态中1的个数y,状态中有多少个猛兽,即状态中1的个数,我们可以预先计算好放入y数组,y[i]=y[i少一个1]+1;最后是攻击范围,每个状态都有自己的攻击范围,在后面需要看这个状态是否与上一行重复,就要看上一行的1是否在攻击范围内,攻击访问包括自己、左边和右边,即i | i<<1 | i>>1。

转移:f[i][j][c] += f[i-1][k][c-y[j,前i行放c个猛兽,第i行状态是j,放了y[j]个猛兽,因此前i-1行放了c-y[j]个猛兽;要能够转移,那么j和k不仅需要是可行状态,而且必须满足k&g[j]为0或者j&g[k]为0,即k不被j攻击到,也就是j也不会被k攻击到。

最终答案就是前n行放了m个猛兽,最后一行的状态可以是任意可行状态。

程序实现

About

坚决不Copy代码!

本文标签:,,,,

SSOJ2157猛兽军团1:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!