题意：
一个炮兵可以攻打和他之间曼哈顿距离为2的士兵，给出你一块n*m的战场，告诉你哪些地方可以站人哪些地方不可以，问你最多可以安放多少个士兵?
n <= 100, m <= 10
思路：
这道题暴力是不可以的，因为状态太多了
可以状态DP来做，用一个数组G记录战场的限制，然后用一个数组dp[当前状态或者是前一个状态][当前状态的十进制表示][前一个状态的十进制表示]
因为用的是G[1<<m]来表示，所以时间复杂度是n*(2^m)*(2^m)*(2^m)，m最多为10，所以时间复杂度就是10*1024*1024*1024，显然这样的时间复杂度也是说不过去的。所以就用一个预处理，预处理出满足基本条件的状态，即水平距离上曼哈顿距离不为2的状态，我用bir[][2]来存预处理出来的基本状态，bir[][0]表示的是预处理的符合基本条件状态的二进制数，bir[][1]表示的是这个状态中1的个数
Tips：
因为用的是滚动数组，所以应该注意n == 1的情况
位运算的优先级比 != 高，所以当我判断是否符合条件的时候应该直接写if(***)或者是if((***) != 0)
不能写 == 1，因为不管是哪种位运算，出来的结果都不一定是1，只能是 != 0
这里还有一个处理状态sta里面有多少个1的有效办法就是用lowbit(x) { return (x)&(-x)}, lowbit(x)可以提取x的最后一个1至最后一个0，这个可以利用补码原理来理解
这样不断 i -= lowbit(i), bir[][1]++, 就可以得到相对应1的个数了
Code:
#include <stdio.h>
#include <cstring>
#include <bitset>
#include <iostream>
#include <algorithm>
using namespace std; int n, m;
int G[], bir[<<|][], top;
int dp[][<<|][<<|];
int ans; int lowbit(int x)
{
return (x)&(-x);
} void init()
{
top = ;
int st = <<;
for (int i = ; i < st; ++i) {
if (((i>>)&i) || ((i<<)&i)) continue;
int tmp = i;
bir[top][] = i;
while (tmp) {
tmp -= lowbit(tmp);
bir[top][]++;
}
top++;
}
} void DP()
{
int st = <<m;
for (int i = ; i < top && bir[i][] < st; ++i)
if ((bir[i][]&(G[]^(st-))) != ) continue; /// == 1!!!!!
else ans = max(ans, bir[i][]); if (n == ) return; for (int i = ; i < top && bir[i][] < st; ++i) {
for (int j = ; j < top && bir[j][] < st; ++j) {
if ( (bir[i][]&(G[]^(st-))) !=
||(bir[j][]&(G[]^(st-))) !=
||((bir[i][]<<)&bir[j][]) || ((bir[i][]>>)&bir[j][])) continue;
dp[][j][i] = bir[i][]+bir[j][];
ans = max(ans, dp[][j][i]);
}
}
// printf("___2___%d\n", ans);
int t = ;
for (int i = ; i < n; ++i) {
for (int j = ; j < top && bir[j][] < st; ++j) {
if (bir[j][]&(G[i-]^(st-))) continue;
for (int k = ; k < top && bir[k][] < st; ++k) {
if (bir[k][]&(G[i-]^(st-))) continue;
for (int l = ; l < top && bir[l][] < st; ++l) {
if ( ((G[i]^(st-))&bir[l][])
||(bir[l][]&bir[j][])
||((bir[l][]<<)&bir[k][])
||((bir[l][]>>)&bir[k][])) continue;
dp[t][l][k] = max(dp[t][l][k], dp[(t+)%][k][j]+bir[l][]);
ans = max(ans, dp[t][l][k]);
}
}
}
t = (t+)%;
}
} int main()
{
// freopen("in.txt", "r", stdin);
init(); while (~scanf("%d %d", &n, &m)) {
ans = -;
memset(dp, , sizeof(dp));
for (int i = ; i < n; ++i) {
int p = , tmp;
for (int j = ; j < m; ++j) {
scanf("%d", &tmp);
if(tmp != ) p |= (<<j); ///!!!!
}
G[i] = p;
}
DP();
printf("%d\n", ans);
}
return ;
}