【POJ】1185 炮兵阵地

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 #define MAXN 110
  6 #define MAXM 66
  7 char s[MAXN][MAXM];
  8 int n,m,size;
  9 int dp[MAXN][MAXM][MAXM];
 10 int h[MAXN],a[MAXN],cnt[MAXN];
 11 inline bool OK(int x)
 12 {
 13     if(x&(x<<1))
 14         return false;
 15     if(x&(x<<2))
 16         return false;
 17     return true;
 18 }
 19 int One(int x)
 20 {
 21     int ans;
 22     for(ans=0;x;x>>=1)
 23     {
 24         if(x&1)
 25             ans++;
 26     }
 27     return ans;
 28 }
 29 void Init()
 30 {
 31     int i;
 32     for(i=size=0;i<(1<<m);i++)
 33     {
 34         if(OK(i))
 35         {
 36             a[size]=i;
 37             cnt[size++]=One(i);
 38         }
 39     }
 40 }
 41 inline bool Unfit(int x,int y)
 42 {
 43     return h[x]&a[y];
 44 }
 45 inline bool Two(int x,int y)
 46 {
 47     return a[x]&a[y];
 48 }
 49 void DoIt()
 50 {
 51     int i,j,k,t,ans;
 52     memset(dp,0,sizeof(dp));
 53     for(i=0;i<size;i++)
 54     {
 55         if(!Unfit(1,i))
 56             dp[1][i][0]=cnt[i];
 57     }
 58     for(i=2;i<=n;i++)
 59     {
 60         for(j=0;j<size;j++)
 61         {
 62             if(Unfit(i,j))
 63                 continue;
 64             for(k=0;k<size;k++)
 65             {
 66                 if(Unfit(i-1,k)||Two(j,k))
 67                     continue;
 68                 for(t=0;t<size;t++)
 69                 {
 70                     if(Unfit(i-2,t)||Two(t,k)||Two(t,j))
 71                         continue;
 72                     dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][t]+cnt[j]);
 73                 }
 74             }
 75         }
 76     }
 77     for(ans=0,i=1;i<=n;i++)
 78     {
 79         for(j=0;j<size;j++)
 80         {
 81             for(k=0;k<size;k++)
 82                 ans=max(ans,dp[i][j][k]);
 83         }
 84     }
 85     printf("%d\n",ans);
 86 }
 87 int main()
 88 {
 89     int i,j;
 90     while(~scanf("%d%d",&n,&m))
 91     {
 92         for(i=1;i<=n;i++)
 93         {
 94             h[i]=0;
 95             for(j=1;j<=m;j++)
 96             {
 97                 scanf(" %c",&s[i][j]);
 98                 if(s[i][j]=='H')
 99                     h[i]+=1<<(j-1);
100             }
101         }
102         Init();
103         DoIt();
104     }
105     return 0;
106 }