题意：在一个N*M的矩阵中的空地放两两不能相互攻击的炮兵，两个炮兵能相互攻击当且仅当它们在同行或同列且距离小于等于2，求最多能摆多少。（N<=100，M<=10）
据说是状压DP经典题。由于一行至多有10列，所以不妨以两行为状态。直接用二进制表示状态（2^10）不可行，因为合法状态只占少数。但我们可以事先搜出所有合法状态。一个小优化是用位运算判断是否能够转移。
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 100, MAX_M = 10;
int N, M, p, st[60], cnt[60], l[MAX_N], f[MAX_N][60][60];
char s[MAX_N];void dfs(int k, int now, int c)
{cnt[p] = c;st[p++] = now;for (int i = k; i < M; ++i)dfs(i+3, now | (1<<i), c+1);
}int main()
{scanf("%d %d", &N, &M);dfs(0, 0, 0);for (int i = 0; i < N; ++i) {scanf("%s", s);for (int j = 0; j < M; ++j)if (s[j] == 'P')l[i] |= 1<<j;}for (int i = 0; i < p; ++i)if ((l[0] | st[i]) == l[0])f[0][0][i] = cnt[i];for (int i = 1; i < N; ++i)for (int j = 0; j < p; ++j)for (int k = 0; k < p; ++k)if (f[i-1][j][k])for (int t = 0; t < p; ++t)if ((l[i] | st[t]) == l[i] && !(st[j] & st[t]) && !(st[k] & st[t]))f[i][k][t] = max(f[i][k][t], f[i-1][j][k] + cnt[t]);int ans = 0;for (int i = 0; i < p; ++i)for (int j = 0; j < p; ++j)ans = max(ans, f[N-1][i][j]);printf("%d\n", ans);return 0;
}