? 这题看到\(m\)极小的范围,以及炮兵特别的攻击范围,基本上就可以确定是状压\(dp\).我们把炮兵当成\(1\),然后就可以用一个二进制数来表示这行炮兵摆放的状态了。但是这道题的状压\(dp\)有一些不同.往常的状压\(dp\)一般只需要考虑当前行对上一行的影响,但是这道题比较特(毒)殊(瘤),炮兵不仅会影响到上一行,还会影响到上上一行,因此只考虑当前行的状态进行\(dp\)是不够的,还得考虑上一行的状态
? 明确了题意之后,状态也就不难定义了.我们用\(f[i][j][k]\)来表示前\(i\)行,第\(i\)行的状态为\(j\),第\(i - 1\)行的状态为\(k\)时最多可以摆放多少个炮兵.状态定义了,那么如何转移呢?
? 不难想到\(f[i][j][k] = max\{f[i - 1][k][z]\}\)
? 最后一个问题,边界条件?
? \(f[1][x][0] = cnt(x)\),\(cnt(x)\)表示统计二进制下数\(x\)中\(1\)的数量
? 方程比较容易想到,那么程序如何实现呢?
献上萌新的代码:程序中萌新实现时,不是直接用的状态,而是这个状态的编号
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 128;
const int maxm = 12;
const int maxs = 1 << maxm;//最多有多少个状态的状态数
int status[maxs],f[2][maxs][maxs],can[maxn],tot,n,m,full;//status表示状态,f为dp数组,can为地形,tot为状态总数(计数器),n,m由题意可知,full为全集
char str[maxm];//字符串临时数组
inline int cnt(int x){//统计二进制下数x里面1的数量
int ret = 0;
while(x){
if(x & 1)ret++;
x >>= 1;
}
return ret;
}
inline int check(int a,int b){
return a & b;
}
inline int check(int a,int b,int c){//a,b,c为三行炮兵摆放的状态,判断是否可行
return check(a,b) | check(a,c) | check(b,c);
}
int main(){
#ifdef LOCAL
freopen("fafa.in","r",stdin);//本机调试用
#endif
scanf("%d %d",&n,&m);
for(int i = 1;i <= n;i++){//读入地形
scanf("%s",str + 1);
for(int j = 1;j <= m;j++)
if(str[j] == 'H')can[i] = (can[i] << 1) | 1;
else can[i] = can[i] << 1;
}
full = (1 << m) - 1;//全集
for(int i = 0;i <= full;i++)//预处理状态
if((!(i & (i << 2))) && (!(i & (i << 1))) && (!(i & (i >> 1))) && (!(i & (i >> 2))))
status[++tot] = i;//如果状态i可行,把它丢进status数组
for(int i = 1;i <= tot;i++)
f[1 % 2][i][1] = cnt(status[i]); //边界条件,1号状态表示没有炮兵(由初始化代码可以看出来)
for(int i = 2;i <= n;i++)
for(int j = 1;j <= tot;j++)
if(!(status[j] & can[i]))//不和地形冲突
for(int k = 1;k <= tot;k++)
if((!(status[k] & can[i - 1])) && (!check(status[j],status[k])))//不和地形冲突,且炮兵不互相冲突
for(int z = 1;z <= tot;z++)
if((!(status[z] & can[i - 2])) && (!check(status[j],status[k],status[z])))//同上
f[i % 2][j][k] = max(f[i % 2][j][k],f[(i - 1) % 2][k][z] + cnt(status[j]));//滚动数组,进行状态转移
int ans = 0;
for(int i = 1;i <= tot;i++)//统计答案
for(int j = 1;j <= tot;j++)
ans = max(ans,f[n % 2][i][j]);
printf("%d\n",ans);
return 0;
}
原文:https://www.cnblogs.com/colazcy/p/11514754.html