题目描述
司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
输入输出格式
输入格式：
第一行包含两个由空格分割开的正整数，分别表示N和M；
接下来的N行，每一行含有连续的M个字符（‘P’或者‘H’），中间没有空格。按顺序表示地图中每一行的数据。N≤100；M≤10。
输出格式：
仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。
输入输出样例
输入样例#1：
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
输出样例#1：
6
题意：
思路：
状压DP
因为每一行要对下面两行有影响，所以我们定义DP状态就要维护前两行状态的信息，即
dp[i][j][k] 代表 到第i行，当前行是第j个状态，上一行是第k个状态，最大的部署数量。
我们知道如果一行有m个方格，那么最多有 2^m 个状态， 而m最大是10，
那么如果我们不进行优化，dp数组要开到 dp[100][1024][1024] 我们应该知道，这个数组太大了，我们是开不到这么大的数组的。
那么我们应该如何优化呢？我们从题目中的一个信息来入手，每一行一个炮台对左右两个位置都有影响，那么减去一行中，两个1的距离最少为3，这样一来合法的状态数量就少之又少。
通过程序我们可以得知，合法的状态数不大于110，那么我们可以枚举 第i合法状态来DP，用一个数组INDEX来存具体的状态信息， 即INDEX[i] 为第i个合法状态的具体状态信息。
这样我们就优化了时空。
状态转移方程为：
dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][w]+num[INDEX[j]]);
细节见代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define dll(x) scanf("%I64d",&x)
#define xll(x) printf("%I64d\n",x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n;
int m;
int a[500];
bool can[(1<<11)];
bool can2[300][123];
int dp[120][123][123];
int ans=0;
int INDEX[maxn];
int cnt=0;
int num[(1<<11)];
int main()
{
// freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
//freopen("D:\\common_text\code_stream\\out.txt","w",stdout);
gbtb;
cin>>n>>m;
char c;
repd(i,1,n)
{
repd(j,1,m)
{
cin>>c;
if(c=='P')
{
a[i]=(a[i]<<1)+1;
}else
{
a[i]=(a[i]<<1);
}
}
}
int maxstate=(1<<m)-1;// 最大状态数
for(int i=0;i<=maxstate;i++)
{
if(((i<<1)&i)==0&&((i<<2)&i)==0&&((i>>2)&i)==0&&((i>>1)&i)==0)// 同一行内两个1之间至少要有两个空格
{
INDEX[++cnt]=i;
can[cnt]=1;
int j=i;
while(j)
{
if(j&1)
{
num[i]++;
}
j>>=1;
}
}
}
// can2[i][j] 代表在第i行中，第j个状态是合法的状态。
for(int i=1;i<=cnt;i++)
{
int x=INDEX[i];
if(((x&a[1])==x))
{
can2[1][i]=1;
dp[1][i][0]=num[x];
}
}
for(int i=1;i<=cnt;++i)
{
if(((INDEX[i]&a[2])==INDEX[i]))
{
can2[2][i]=1;
for(int j=1;j<=cnt;++j)
{
if(can2[1][j])
{
if((INDEX[i]&INDEX[j])==0)
{
dp[2][i][j]=max(dp[2][i][j],dp[1][j][0]+num[INDEX[i]]);
}
}
}
}
}
for(int i=3;i<=n;++i)
{
for(int j=1;j<=cnt;j++)
{
if(((INDEX[j]&a[i])==INDEX[j]))
{
can2[i][j]=1;
for(int k=1;k<=cnt;k++)
{
if(can2[i-1][k])
{
if((INDEX[k]&INDEX[j])==0)
{
for(int w=1;w<=cnt;++w)
{
if(can2[i-2][w])
{
if((INDEX[w]&INDEX[j])==0&&(INDEX[w]&INDEX[k])==0)// 和上面两行均没重合的1
dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][w]+num[INDEX[j]]);
}
}
}
}
}
}
}
}
for(int i=1;i<=cnt;++i)
{
for(int j=1;j<=cnt;j++)
{
ans=max(ans,dp[n][i][j]);
}
}
cout<<ans<<endl;
return 0;
}
inline void getInt(int* p) {
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '0');
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 - ch + '0';
}
}
else {
*p = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 + ch - '0';
}
}
}