A了一整天~~~终于搞掉了。

　　真是血都A出来了。

　　题目意思很清楚，肯定是状压DP。

　　我们可以联系一下POJ 1185 炮兵阵地，经典的状压DP。

　　两道题的区别就在于，这道题的攻击是可以被X挡住的，而且攻击的范围不同。

　　这是这道题的攻击范围。

　　但是这个攻击范围是会被X挡住的。

　　所以得在1185上加以改进。

　　分析：

　　POJ 1185，因为可以隔着障碍物打，所以他每行的状态是一样的，但是这题由于攻击会被挡住，所以每行的状态是不一样的，所以我们预处理的时候就要处理出每一行的状态数，分别保存，然后存下每行每个状态的数量。

　　因为我的下标是从0开始的，所以我得预先处理一下第0行和第1行的状态转移过程，这个很好处理，具体看代码。

　　那么预处理完毕之后就是状态转移的过程。

　　变量定义：

　　M[i] ：每一行的地图压缩。

　　st[i][j] ：第j行，第i个状态。

　　Count[i][j] ：第j行第i个状态的数量。

　　num[i]：第i 行状态的总数。

　　dp[i][j][k] ：第i行的状态是k ,第i - 1 行的状态是j的可行状态总数。

　　这道题貌似还卡内存，必须使用滚动数组，因为状压的时候他只需要3个状态，所以这里i开到3就可以了。

　　状态转移的过程，首先当前状态是k ,上一状态是j，上上状态是l 。

　　那么首先判断k 和 j的状态可行性，首先j不能出现在k的上方，那就是(st[j][i - 1] & st[k][i]) ，然后k 也不能出现在j的左下和右下的位置，通过上图可以看出，k不能出现在j的左移一位，右移一位的位置。那么可以这么判断(st[j][i - 1] >> 1 & st[k][i]), (st[j][i - 1] << 1 & st[k][i]) 。这样就处理完j 和k 这两个状态了。

　　接下来是j和l，这里的判断同j和k，因为都是相邻的两行，这里不多说了，一样的，下面着重讲一下l和k的状态的判断。

　　因为l和k之间是可能隔着X的，所以我们不能直接判断，而应该判断他们之间是否有X。

　　比如判断l是否在k上方，那么不能直接(st[l][i - 2] & st[k][i])，因为他们之间如果有X，那么该状态是成立的。

　　那么到底如何判断呢。昨天我也是在这里卡住了，今天早上突然想到，其实我们只要判断l状态和k状态都是1的位置，那么他们的i - 1行该位置是否是X就行了。而判断X我们可以直接使用压缩过的地图进行判断。

　　那么可以这样：

　　int s = (st[l][i - 1] & st[k][i]) ;

　　if(s & M[i - 1] != s)

　　那么就证明他们之间是会互相攻击的，s & (M[i -1] ) != s，就说明l和k都为1的位置他们中间至少有一处不为X，那么该状态不可行。

　　同理我们可以判断 l状态的左下攻击和右下攻击是否会打到k状态。

　　如果是左下攻击，那么只需要将l状态左移两位与k判断，然后判断他们的之间是否有X。具体看代码，我就不多解释了，相信自己动手画张图还是很好理解的。

　　同理右下攻击。