先放一下原初的代码,然后讲一下我给大家娓娓道来卡空间的经过()
#include<iostream>
#include<cstdio>
#define lowbit(x) x&-x
int tot,status;
char ch[105];
int f[105][1005][1005];//1:第几行 2:状态(前一行) 3:状态
int n,m,s[1005],g[1005],map[105];
int ans;
inline int count(int x){//计算某一状态1的个数
int sum=0;
while(x)
++sum,x-=lowbit(x);
return sum;
}
inline void init1(){
for(register int i=0;i<=(1<<m)-1;++i)
if(((i&(i<<1))==0)&&((i&(i<<2))==0)&&((i&(i>>1))==0)&&((i&(i>>2))==0)){
//判断每个1左右是否有,即判断合法状态
++status;
s[status]=i,g[status]=count(i);
if((i&map[1])==0)
f[1][0][status]=g[status];//初始化第一行
}
return;
}
inline void init2(){//第二行
for(register int i=1;i<=status;++i)//status第一行
for(register int j=1;j<=status;++j)//status第二行
if(((s[j]&map[2])==0)&&((s[i]&s[j])==0))
f[2][i][j]=std::max(f[2][i][j],f[1][0][i]+g[j]);
}
//inline void print(){
// for(register int i=1;i<=n;++i){
// for(register int j=1;j<=status;++j){
// for(register int k=1;k<=status;++k)
// cout<<f[i][j][k]<<" ";
// cout<<endl;
// }
// cout<<endl;
// }
// return;
//}
signed main(){
//读入
std::ios::sync_with_stdio(false);
std::cin>>n>>m;
for(register int i=1;i<=n;++i){
std::cin>>ch;
for(register int j=0;j<m;++j)
if(ch[j]=='H')
map[i]+=1<<j;//存储每一行不能放炮兵的位置
}
init1();//初始化1
init2();//初始化第二行
for(register int i=3;i<=n;++i)//当前行数
for(register int j=1;j<=status;++j) //当前行状态
if((map[i]&s[j])==0)//地形
for(register int k=1;k<=status;++k)//前一行
if((s[k]&s[j])==0)
for(register int q=1;q<=status;++q)//前两行
if(((s[q]&s[k])==0)&&((s[q]&s[j])==0))
f[i][k][j]=std::max(f[i][k][j],f[i-1][q][k]+g[j]);
// print();
for(register int i=1;i<=status;++i)
for(register int j=1;j<=status;++j)
ans=std::max(f[n][i][j],ans);
std::cout<<ans<<std::endl;
return 0;
}