POJ 3254 炮兵阵地(状态压缩DP)

时间:2021-11-29 16:49:59

题意:由方格组成的矩阵,每个方格可以放大炮用P表示,不可以放大炮用H表示,求放最多的大炮,大炮与大炮间不会互相攻击。大炮的攻击范围为两个方格。

分析:这次当前行的状态不仅和上一行有关,还和上上行有关,所以用三维dp【i】【j】【k】来表示第i行的状态为j,i-1行状态为k时最多的大炮。

一开始看数据量为100 * 1024 * 1024 铁定要爆,但是由于大炮的攻击方式,单独看每一行最多只有几十种可行的状态,所以保存好这些状态就行了。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int n,m,sum;
int dp[105][1 << 7][1 << 7]; // dp【i】【j】【k】来表示第i行的状态为j,i-1行状态为k时最多的大炮
int buff[1 << 6]; // 存状态
int bar[105]; // 存障碍
int num[1 << 6]; // 存每种状态中1的个数,即为大炮的个数
char map[105][11];
void init() {
memset(bar,0,sizeof(bar));
memset(dp,0,sizeof(dp));
memset(buff,0,sizeof(buff));
memset(num,0,sizeof(num));
sum = 0;
}
void barrier() {
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(map[i][j] == 'H') {
int move = m - j - 1;
bar[i] += (1 << move);
}
}
}
} bool judge(int s) {
while(s) {
if(s & 1) {
if(((s >> 1) & 1) || ((s >> 2) & 1)) return false;
}
s = s >> 1;
}
return true;
} void getbuff() {
int total = 1 << m;
for(int i=0; i<total; i++) {
if(judge(i)) buff[sum++] = i;
}
} int cal(int s) {
int cnt = 0;
while(s) {
if(s & 1) cnt ++;
s = s >> 1;
}
return cnt;
} void getnum() {
for(int i=0; i<sum; i++) {
num[i] = cal(buff[i]);
}
}
int main() {
scanf("%d%d",&n,&m);
init();
for(int i=0; i<n; i++) scanf("%s",map[i]);
barrier();
getbuff();
getnum();
for(int i=0; i<n; i++) {
for(int j=0; j<sum; j++) {
if(bar[0] & buff[j]) continue;
for(int k=0; k<sum; k++) {
dp[0][j][k] = num[j];
}
}
}
for(int i=1; i<n; i++) {
for(int j=0; j<sum; j++) {
if(bar[i] & buff[j]) continue;
for(int k=0; k<sum; k++) {
if(bar[i-1] & buff[k]) continue;
if((buff[j] & buff[k])) continue;
for(int l=0; l<sum; l++) {
if(i != 1) {
if(bar[i-2] & buff[l]) continue;
if(buff[k] & buff[l] || buff[j] & buff[l]) continue;
}
dp[i][j][k] = max(dp[i][j][k],
dp[i-1][k][l] + num[j]);
}
}
}
}
int ans = 0;
for(int i=0; i<n; i++) {
for(int j=0; j<sum; j++) {
for(int k=0; k<sum; k++) {
ans = max(ans,dp[i][j][k]);
}
}
}
printf("%d\n",ans);
return 0;
}