炮兵阵地 状压dp

炮兵阵地 状压dp"/>

炮兵阵地 状压dp

题目链接

题意：在 n × m n×m n×m的方格中，放置炮兵部队，炮兵部队可以攻击上下左右两格的距离，如何放置使炮兵部队不能够相互攻击，并且使放置的部队数目最大。

状态压缩dp：
将每行的放置的部队压缩成一个二进制的状态数。
如果对每行来说，有三个连续的格子有两个放置部队这样的情况是不合法的。
同时上下连续三格有两格放置部队也是不合法的

#include<bits/stdc++.h>
using namespace std;
const int N = 11,M = 1<<10;
vector<int>state;
int g[105],cnt[M];
int n,m;
int f[2][M][M];//使用滚动数组
bool check(int x)
{for(int i=0;i<=m;i++)if((x>>i&1)&&((x>>i+1&1)||(x>>i+2&1)))return false;return true;
}
int count(int x)
{int res = 0;for(int i=0;i<m;i++) res += x>>i & 1;return res;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)for(int j=0;j<m;j++){char c;cin>>c;if(c=='H') g[i] += 1 << j;}for(int i=0;i< 1<<m;i++)if(check(i)){state.push_back(i);cnt[i] = count(i);}for(int i=1;i<=n+2;i++)for(int j=0;j<state.size();j++)for(int k=0;k<state.size();k++)for(int u=0;u<state.size();u++){int a = state[j],b = state[k],c = state[u];if((a&b)||(b&c)||(a&c)) continue;//上下连续三格不能出现两格if(g[i-1]&a||g[i]&b) continue;//高地不能放置部队f[i&1][j][k] = max(f[i&1][j][k],f[i-1&1][u][j]+cnt[b]);}cout<<f[n+2&1][0][0]<<'\n';return 0;
}