SSOJ2157猛兽军团1
3246+
作者：crxis 发布：2018-01-17 分类：状压DP
题目大意：猛兽会攻击自身周围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个猛兽，最后一行的状态可以是任意可行状态。
程序实现
