poj1185--炮兵阵地

经典的状态压缩dp，有几个点要注意

1）必须用三维的状态才能合理的进行状态的转移，用二维的状态约束性不够

2）初始化是必须要同时初始化前两行的所有状态

3）注意位运算的使用。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int total[1000],cur[110];
int dp[110][200][200];
int top,n,m;
int c[100];

int ok(int x,int y)
{
    if(x&y)
        return 0;
    return 1;
}

int cnt(int x)
{
    int d=0;
    while(x>0)
    {
        if(x&1)
          d++;
        x=x>>1;
    }
    return d;
}

void Allstate()
{
    top=1;
    int k=(1<<m);
    for(int i=0;i<k;i++)
    {
        if(((i<<1)&i)||((i<<2)&i))
            continue;
        total[top++]=i;
    }
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
         Allstate();
         char str[20];
         memset(cur,0,sizeof(cur));
         for(int i=1;i<=n;i++)
         {
             scanf("%s",str+1);
             int x=0;
             for(int j=1;j<=m;j++)
             {
                 if(str[j]=='P')
                   x=x*2+1;
                 else
                   x=x*2;
             }
             cur[i]=~x;
         }
         memset(dp,0,sizeof(dp));
         for(int i=1;i<top;i++)
             c[i]=cnt(total[i]);
         for(int i=1;i<top;i++)
         {
             if(ok(total[i],cur[1]))
                  dp[1][i][0]=c[i];
         }
         for(int i=1;i<top;i++)
         {
             if(ok(total[i],cur[2])==0)
                 continue;
             for(int j=0;j<top;j++)
             {
                 if(ok(total[j],cur[1])==0)
                     continue;
                 if(ok(total[i],total[j])==0)
                     continue;
                 dp[2][i][j]=max(dp[2][i][j],dp[1][j][0]+c[i]);
             }
         }
         for(int i=3;i<=n;i++)
           for(int j=1;j<top;j++)
           {
               if(ok(cur[i],total[j])==0)
                  continue;
               for(int d1=0;d1<top;d1++)
               {
                   if(ok(cur[i-1],total[d1])==0)
                      continue;
                   if(ok(total[d1],total[j])==0)
                      continue;
                   for(int d2=0;d2<top;d2++)
                   {
                       if(ok(cur[i-2],total[d2])==0)
                          continue;
                       if(ok(total[d2],total[j])==0)
                          continue;
                       if(ok(total[d2],total[d1])==0)
                          continue;
                        dp[i][j][d1]=max(dp[i][j][d1],dp[i-1][d1][d2]+c[j]);
                   }
               }
           }
         int ans=0;
         for(int i=1;i<top;i++)
           for(int j=0;j<top;j++)
              ans=max(ans,dp[n][i][j]);
         printf("%d\n",ans);
    }
  return 0;
}
文章转自