炮兵阵地 POJ 1185

n*m

P 和 M

P可以放人 M不行

人不能相互打到 问最多可以放多少人

#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<math.h>

#include<map>

using namespace std;

#define MAXN 1<<10

char z[][];

int x[];

int dp[][][];

int num[];

int cn[];

int Count(int a)

{

    int ans=;

    while(a>)

    {

        if(a&)

            ans++;

        a=a>>;

    }

    return ans;

}

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        for(int i=;i<n;i++)

            scanf("%s",z[i]);

        memset(x,,sizeof(x));

        memset(dp,-,sizeof(dp));

        int cnt=;

        int en=<<m;

        for(int i=;i<en;i++)

            if(((i&(i<<))||(i&(i<<)))==)

            {

                cn[cnt]=Count(i);

                num[cnt++]=i;

            }

        for(int i=;i<n;i++)

        {

            for(int j=;j<m;j++)

                if(z[i][j]=='H')

                    x[i]|=(<<j);

        }

        for(int i=;i<cnt;i++)

        {

            if(x[]&num[i])

                continue;

            dp[][i][]=cn[i];

        }

        for(int i=;i<n;i++)  //行

        {

            for(int j=;j<cnt;j++)  //这行的状态

            {

                if(x[i]&num[j]) //不能矛盾

                    continue;

                for(int k=;k<cnt;k++) //上一行的状态

                {

                    if(num[j]&num[k]) //相邻两行不能同时出现1

                        continue;

                    for(int k1=;k1<cnt;k1++) //上面第二行状态

                    {

                        if(num[j]&num[k1]) //相邻两行不能同时出现1

                            continue;

                        if(dp[i-][k][k1]==-)

                            continue;

                        dp[i][j][k]=max(dp[i][j][k],dp[i-][k][k1]+cn[j]);

                    }

                }

            }

        }

        int ans=;

        for(int i=;i<cnt;i++)

            for(int j=;j<cnt;j++)

                ans=max(dp[n-][i][j],ans);

        printf("%d\n",ans);

    }

    return ;

}