hdu 4539(状压dp)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4539

思路：跟poj1185简直就是如出一辙！

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int row[];

 int dp[][][];

 int s[<<];

 int num[<<];

 int n,m,state,ans,x;

 int Get_Num(int x)

 {

     int cnt=;

     while(x>){

         cnt++;

         x=x&(x-);

     }

     return cnt;

 }

 int main()

 {

     while(~scanf("%d%d",&n,&m)){

         memset(row,,sizeof(row));

         memset(dp,,sizeof(dp));

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

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

                 scanf("%d",&x);

                 if(!x)row[i]=(row[i]<<)|;

                 else row[i]<<=;

             }

         }

         state=;

         for(int i=;i<(<<m);i++){

             if(i&(i<<))continue;

             s[state]=i;

             num[state++]=Get_Num(i);

         }

         for(int i=;i<state;i++){

             if(s[i]&row[])continue;

             dp[][i][]=num[i];

         }

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

             for(int j=;j<state;j++){

                 if(s[j]&row[i])continue;

                 for(int k=;k<state;k++){  //i-1行信息

                     if((s[j]&(s[k]>>))||(s[j]&(s[k]<<)))continue;//曼哈顿距离为2冲突

                     for(int l=;l<state;l++){  //i-2行信息

                         if(s[j]&s[l])continue;

                         if((s[k]&(s[l]>>))||(s[k]&(s[l]<<)))continue;//曼哈顿距离为2冲突

                         dp[i][j][k]=max(dp[i][j][k],dp[i-][k][l]+num[j]);

                     }

                 }

             }

         }

         ans=;

         for(int i=;i<state;i++){

             for(int j=;j<state;j++){

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

             }

         }

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

     }

     return ;

 }