Solution [NOI2001]炮兵阵地
题目大意:在(n)行(m)列的地图上,在炮兵不与地形冲突,并且炮兵之间不互相冲突的前提下摆放尽可能多的炮兵.求最多可以摆放多少个炮兵
状压(dp)
这题看到(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)的数量
方程比较容易想到,那么程序如何实现呢?
- 如何判断炮兵与地形是否冲突?
把题目中的山地(也就是不能摆放炮兵的地方)用(1)来表示,这样就可以用一个二进制数来表示每行的地形状态.然后拿地形状态与这行的炮兵摆放状态做一个(and)(按位与)运算.如果(and)的结果是(0)的话,那就说明炮兵不与地形冲突 - 如何判断炮兵之间是否互相冲突?
判断两行炮兵是否冲突,也只需要将它们做一个(and)运算即可.同上,如果运算结果是(0)的话,那就说明炮兵不互相冲突 - 预处理
为了加快程序速度,我们可以先预处理出可能的状态(比如两个炮兵如果紧挨着的话按照题意是不行的).对于一个表示炮兵摆放的二进制数(x),我们可以将(x)与(x << 2), (x << 1), (x >> 1), (x >> 2) 分别做一个(and)运算,如果结果都为(0)就说明这种方案合法 - 空间消耗
我们发现,如果直接开一个数组,其空间占用约(100 imes 1024 imes 1024 = 104857600)个(int),消耗空间约(400MB).但是题目空间限制(128MB),空间会炸.但是看一看我们的状态转移方程,我们会发现:计算第(i)行只会用到第(i - 1)行的状态,因此我们可以用滚动数组来大幅优化空间开销
优化后的空间占用:(2 imes 1024 imes 1024 = 2097152)个(int),约(8MB).绰绰有余
献上萌新的代码:程序中萌新实现时,不是直接用的状态,而是这个状态的编号
#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
",ans);
return 0;
}