此题是练习ka空间的一个好题

先放一下原初的代码，然后讲一下我给大家娓娓道来卡空间的经过（）

#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;
}