题意:给出一张n * m的地图,其中 有的地方能放大炮,有的地方不能,大炮与上下左右两个单位范围内会相互攻击,问最多能放几个大炮
能放大炮为1不能放大炮为0,把每一行看做一个状态,要除去同一行与前面两个相邻的情况,然后在除去与上面两行相邻的情况,因为涉及前面两行所以多设一维状态
dp[i][j][k]表示 第 i 行 状态为k时,第i - 1行状态为j,
那么dp[i][j][k] = max ( dp[i][j][k], dp[i - 1][t][j] + num[k]); num[k]表示第i行可以放多少门大炮,也就是k状态下1的个数
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int state[], num[];
int cur[];
char g[][];
int dp[][][];
int n, m, top, total;
inline bool is_ok(int x)
{
if (x & (x << ))
return ;
if (x & (x << ))
return ;
return ;
}
int jcount(int x)
{
int cnt = ;
for (int i = ; i < ; i++)
if (x & ( << i))
cnt++;
return cnt;
}
int fit(int x, int i)
{
if (x & cur[i])
return ;
return ;
}
void init()
{
top = ;
total = << m;
for (int i = ; i < total; i++)
{
if (is_ok(i))
state[++top] = i;
}
}
int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
init();
for (int i = ; i <= n; i++)
{
cur[i] = ;
scanf("%s", g[i] + );
for(int j = ; j <= m; j++)
if (g[i][j] == 'H')
cur[i] += ( << (j - ) );
//同上一题一样将不能放炮的设为1,这样 & 的话只要非0就不行,因为一定含有不能放炮的而放炮了,0是允许放炮,但是放不放都行,也就是0,1随便,都是可以的
}
memset(dp, -, sizeof(dp));
int ans = -;
for (int i = ; i <= top; i++)
{
num[i] = jcount(state[i]); // 求出每一种状态下能放得炮数
if (!fit(state[i], ))
continue;
dp[][][i] = num[i]; //第一行状态为state[i],第0行状态为state[1] = 0
ans = max(ans, num[i]);
}
for (int i = ; i <= n; i++)
{
for (int t = ; t <= top; t++)
{
if (!fit(state[t], i))
continue;
for (int j = ; j <= top; j++) // 第 i - 1行的情况
{
if (state[t] & state[j])
continue;
for (int k = ; k <= top; k++) //第i - 2行的情况
{
if (state[t] & state[k])
continue;
if (dp[i - ][k][j] != -) // 不符合要求的,dp[1][1][其他] ,而第0行其他状态都没有
{
dp[i][j][t] = max(dp[i][j][t], dp[i - ][k][j] + num[t]);
ans = max(ans, dp[i][j][t]);
}
}
}
}
}
printf("%d\n", ans);
}
return ;
}