我不是导神 @ 2018-10-04 18:34:57
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 1<<30
using namespace std;
int n,m;
char a[105][15];
int f[105][1<<11][1<<11],cont[1<<11],vaild[105][1<<11];
int s[1<<11];
//s[]表示相邻两个一的距离不小于三的所有位二进制集合
//cont[]表示m为二进制数x中有多少个1
//vaild[]表示x属于s,且x中的每个1对应的第i行是否都为平原
//f[i][j][k]表示第i行压缩后状态为j,第i-1行压缩后状态为k是,前i行最多放多少个炮兵
void pretreat();
int main() {
memset(f,-INF,sizeof(f));
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++) {
char array[105];
scanf("%s", array+1);
for(int j = 1; j <= m; j++) {
a[i][j] = array[j];
}
}
pretreat();
int ans;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= 1<<m; j++) {
for(int k = 1; k <= 1<<m; k++) {
if((j&k==0)&&vaild[i][j]&&vaild[i-1][k]) {
for(int l = 1; l <= 1<<m; l++) {
ans = 0;
ans = max(ans,f[i-1][k][l]);
}
f[i][j][k] = ans + cont[j];
}
}
}
}
int sum = 0;
for(int j = 0; j <= 1<<m; j++) {
for(int k = 0; k <= 1<<m; k++) {
if((j&k==0)&&vaild[n][j]&&vaild[n-1][k]) {
sum = max(sum,f[n][j][k]);
}
}
}
printf("%d",sum);
return 0;
}
//预处理
void pretreat() {
memset(s,0,sizeof(s));
memset(vaild,0,sizeof(vaild));
for(int i = 1; i <= 1<<m; i++) {
for(int j = 1; j <= m; j++) {
if(i>>j&1) {
if(((i>>j&1)&(i>>j+1&1)) == 0 && ((i>>j&1)&(i>>j+2&1)) == 0) {
s[i] = 1;
}
}
}
}
for(int i = 1; i <= 1<<m; i++) {
if(s[i]) {
for(int j = 1; j <= m; j++) {
if(i>>j&1) cont[i]++;
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= 1<<m; j++) {
if(s[j]) {
for(int k = 1; k <= m; k++) {
if((j>>k&1)) {
if(a[i][k] != 'P') break;
else vaild[i][j] = 1;
}
}
}
}
}
}
by zzqDeco @ 2018-10-04 18:36:07
@冲段少年 太难了
by 我不是导神 @ 2018-10-04 19:05:26
@zzqzzqzzq 什么太难?
by zzqDeco @ 2018-10-04 19:58:40
@冲段少年 什么都难