记录编号	174072	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]炮兵阵地	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	0.158 s
提交时间	2015-07-31 10:50:10	内存使用	4.34 MiB

#define Max(a,b)((a)>(b)?(a):(b))

#include<cstdio>

using namespace std;

int n,m;
int a[105][100];
int gs[105],b[105];
char s[15];
int y[1025],ans;
int f[105][100][100];//第i行，当前行状态为j，上一行状态为k 

bool judge(int x,int o)
{
    if((x&(x>>1)))
        return 0;
    if((x&(x>>2)))
        return 0;
    if(x&b[o])
        return 0;
    return 1;
}

int main()
{
    freopen("cannon.in","r",stdin);
	freopen("cannon.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        for(int j=1;j<=m;j++)
        {
            if(s[j]=='P')
                b[i]=b[i]|(0<<(m-j));
            else
                b[i]=b[i]|(1<<(m-j));
        }
    }
    for(int i=1;i<=n;i++)//可行状态 
        for(int j=0;j<(1<<m);j++)
        {
            if(judge(j,i))
                a[i][++gs[i]]=j;
        } 
    for(int i=0;i<(1<<m);i++)//求各个状态中1的个数 
    {
        if(  (! (i&(i>>1) ))&&(! (i&(i>>2) ) ))
        {
            int k=i;
            while(k)
            {             
                k-=k&(-k);
                y[i]++;
            }
        }
    }
    for(int i=1;i<=gs[1];i++)
    {    
         f[1][i][0]=y[a[1][i]];
         if(n==1)
             ans=Max(ans,f[1][i][0]);
    }
    for(int i=1;i<=gs[2];i++)
        for(int j=1;j<=gs[1];j++)
        {    
            if(a[2][i]&a[1][j])
                continue;  
            f[2][i][j]=y[a[2][i]]+y[a[1][j]];
            if(n==2)
                ans=Max(ans,f[2][i][j]);
        }
    for(int i=3;i<=n;i++)
        for(int j=1;j<=gs[i];j++)
        {    
            for(int k=1;k<=gs[i-1];k++)
            {   
                if(a[i][j]&a[i-1][k])
                    continue; 
                for(int q=1;q<=gs[i-2];q++)
                {
                    if(a[i][j]&a[i-2][q])
                        continue;
                    if(a[i-1][k]&a[i-2][q])
                        continue;
                    if(f[i-1][k][q]+y[a[i][j]]>f[i][j][k])       
                        f[i][j][k]=f[i-1][k][q]+y[a[i][j]];   
                }
                ans=Max(ans,f[i][j][k]);  
            }
        }
    printf("%d",ans);
}