HDU4539+状态压缩DP

 /*

 题意：n行m列的矩阵，1表示可以放东西，0表示不可以。曼哈顿距离为2的两个位置最多只能有一个位置放东西。

 问最多放多少个东西。

 */

 #include<stdio.h>

 #include<string.h>

 #include<stdlib.h>

 #include<algorithm>

 #include<iostream>

 #include<queue>

 #include<stack>

 #include<math.h>

 #include<map>

 using namespace std;

 const int maxn = ;

 const int maxm = ;

 const int N = ;

 int mat[ maxn ];

 int dp[ maxn ][ N ][ N ];

 int state[ N ];

 int ones_state[ N ];

 int Count_ones( int x ){

     int cnt = ;

     while( x ){

         if( x& )

             cnt++;

         x>>=;

     }

     return cnt;

 }

 int init( int n,int m ){

     memset( state,,sizeof( state ) );

     memset( ones_state,,sizeof( state ) );

     int M = <<m;

     int cnt = ;

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

         if( (i&(i<<))==&&(i&(i>>))== ){

             state[ cnt ] = i;

             ones_state[ cnt ] = Count_ones( i );

             cnt++;

         }

     }

     //printf("cnt=%d\n",cnt);最多169种状态！！

     return cnt;

 }

 void DP( int cnt,int n,int m ){

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

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

             if( (state[i]&mat[])== )

                 dp[][i][] = ones_state[ i ];

         }//初始化

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

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

             if( (state[j]&mat[i])== ){

                 for( int k=;k<cnt;k++ ){

                     if( (state[j]&(state[k]<<))==&&(state[j]&(state[k]>>))== ){

                         for( int k2=;k2<cnt;k2++ ){

                             if( dp[i-][k][k2]==- ) continue;

                             if( (state[j]&state[k2])==&&(state[k]&(state[k2]>>))==&&(state[k]&(state[k2]<<))== )

                                 dp[ i ][ j ][ k ] = max( dp[i][j][k],dp[i-][k][k2]+ones_state[j] );

                         }

                     }

                 }

             }

         }

     }

 }

 int main(){

     int n,m;

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

         int cnt = init( n,m );

         memset( mat,,sizeof( mat ) );

         int tmp;

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

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

                 scanf("%d",&tmp);

                 if( tmp== ){

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

                 }

             }

         }

         DP( cnt,n,m );

         int ans = ;

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

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

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

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

     }

     return ;

 }