记录编号	581058	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]炮兵阵地	最终得分	100
用户昵称	在大街上倒立游泳	是否通过	通过
代码语言	C++	运行时间	0.286 s
提交时间	2023-07-28 16:26:48	内存使用	10.20 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,m,s[105],c[105],p,a[105];
long long f[105][105][105];//f[i][j][k] 表示第i行状态为s[j]、第i-1行状态为s[k]时前i行至多能布置的炮兵阵地个数
long long gcd(long long x,long long y){
    if(x<y) swap(x,y);
    if(x%y==0) return y;
    return gcd(y,x%y);
}
bool pd(long long x){
    if(x&(x<<1)) return false;
    if(x&(x<<2)) return false;
    return true;
}
int main(){
    freopen("cannon.in","r",stdin);
   freopen("cannon.out","w",stdout);
    cin>>n>>m;
    for(long long i=0;i<=(1<<m)-1;i++){
        if(pd(i)) {
            s[++s[0]]=i;
            for(long long t=i;t;t-=t&(-t)) c[s[0]]++;
        }
        
    }
    char fz;
    for(long long i=1;i<=n;i++){
        for(long long j=1;j<=m;j++){
            cin>>fz;
            a[i]=a[i]*2+(fz=='H');
        }
    }
    for(long long i=1;i<=n;i++){
        for(long long j=1;j<=s[0];j++){
            if(!(s[j]&a[i])){
                for(long long k=1;k<=s[0];k++){
                    if(!(s[k]&(a[i-1]|s[j]))){
                        for(long long l=1;l<=s[0];l++){
                            if(!(s[l]&(s[k]|s[j]|a[i-2]))){
                                f[i][j][k]=max(f[i][j][k],f[i-1][k][l]+c[j]);
                            }
                        }
                    }
                }
                
                
                
                
                
                
                
                
                /*for(long long k=c[j];k<=p;k++){
                for(long long l=1;l<=s[0];l++){
                    if((!(s[l]&s[j]))&&k-c[j]>=c[l]){
                        f[i][j][k]+=f[i-1][l][k-c[j]];
                        }
                    }
                }*/
            }
        }
    }
    long long ans=0;
    for(long long j=1;j<=s[0];j++){
        for(long long k=1;k<=s[0];k++){
                ans=max(ans,f[n][j][k]);
            }
        }
    cout<<ans;
    return 0;
}