状態圧縮dp hdu 4539鄭工場長シリーズ物語——排兵布陣

タイトルリンク:
http://acm.hdu.edu.cn/showproblem.php?pid=4539
タイトル:
行列をあげて、兵士を置くことができない位置があります.各兵士はハミルトニアン距離がちょうど2のすべての位置を攻撃することができる.最大何人の兵士を置くことができて、兵士の間で衝突しないようにします.
問題解決の考え方:
状態圧縮dp.
現在位置は前の2行に関係するため,隣接する2行を2次元状態とし,i−2行目を列挙するとi行目の状態が得られる.
記状態dp[][i][j]は、現在の行状態がiであり、前の行状態がjの場合、最大で放せる兵士の数を示す.
dp[][i][j]=Cal(i)+max(dp[][j][k]);
コード:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
#define Maxn 110
int dp[2][1<<10][1<<10];
int save[Maxn];

int Cal(int st) //  1   
{
   int res=0;
   while(st)
   {
      if(st&1)
         res++;
      st>>=1;
   }
   return res;
}

int main()
{
   int n,m,tmp;

   while(~scanf("%d%d",&n,&m))
   {
      for(int i=1;i<=n;i++)
      {
         save[i]=0;
         for(int j=0;j<m;j++)
         {
            scanf("%d",&tmp);
            if(!tmp) //0     ，    1       0  
               save[i]|=(1<<j);
         }
      }
      memset(dp,0,sizeof(dp));
      int lim=1<<m;
      for(int i=0;i<lim;i++)
      {
         if((i&(i<<2))||(i&save[1])) //     
            continue;
         dp[1][i][0]=Cal(i); //        0,      
      }

      int la=1,cur;
      for(int i=2;i<=n;i++)
      {
         cur=la^1;
        // memset(dp[cur],0,sizeof(dp[cur]));
         for(int j=0;j<lim;j++)
         {
            if((j&(j<<2))||(j&save[i])) //     
               continue;
            for(int k=0;k<lim;k++)
            {
               if((k&(k<<2))||(k&save[i-1])) //           
                  continue;
               if(j&(k<<1))
                  continue;
               if(j&(k>>1))  //              
                  continue;
               dp[cur][j][k]=Cal(j); //  1   
               int Max=0;
               for(int p=0;p<lim;p++)
               {
                  if((p&(p<<2))||(p&save[i-2]))
                     continue;
                  if((k&(p<<1))||(j&p)) //i-2  i-1    
                     continue;
                  if(k&(p>>1)) //i-2  i    
                     continue;

                  Max=max(Max,dp[la][k][p]);
               }
               dp[cur][j][k]+=Max;
            }
         }
         la=cur;
      }
      int ans=0;
      for(int i=0;i<lim;i++)
         for(int j=0;j<lim;j++) //           0
            ans=max(ans,dp[cur][i][j]);
      printf("%d
",ans);


   }
   return 0;
}