HDU 2442

状态压缩DP ， 和HDU2280极其相似

 #include <cstdio>
 #include <cstring>
 #include <iostream> using namespace std;
 const int N = ;
 int dp[N][<<][<<] , n , m; //s 表示当前第i行的状态 , u表示上一行状态 , v表示上上行的状态 , cnt表示到当前位置时总共占据的空间
 void dfs(int s , int u , int v , int cnt , int k , int i) //由右到左，访问到第i行的第k位数字
 {
     if(k >= m){
         dp[i][u][s] = max(dp[i][u][s] , cnt);
         return;
     }
     if(k > ){
         if(!(s & (<<k)) && !(u & (<<k-)) && !(v & (<<k)))
             dfs(s | (<<k) , u | (<<k-) , v | (<<k) , cnt +  , k+ , i);
         if(!(s & (<<k)) && !(u & (<<k)) && !(v & (<<k-)))
             dfs(s | (<<k) , u | (<<k) , v | (<<k-) , cnt +  , k+ , i);
     }
     if(k > ){
         if(!(s & (<<k-)) && !(u & (<<k-)) && !(v & (<<k-)))
             dfs(s | (<<k-) , u | (<<k-) , v | (<<k-) , cnt +  , k+ , i);
         if(!(s & (<<k-)) && !(u & (<<k-)))
             dfs(s | (<<k-) , u | (<<k-) , v , cnt +  , k+ , i);
         if(!(s & (<<k)) && !(u & (<<k-)))
             dfs(s | (<<k) , u | (<<k-) , v , cnt +  , k+ , i);
     }
     dfs(s, u , v , cnt , k+ , i);
 } void dfs2(int s , int u , int cnt , int k)
 {
     if(k >= m){
         dp[][u][s] = max(dp[][u][s] , cnt);
         return;
     }
     if(k > ){
         if(!(s & (<<k-)) && !(u & (<<k-)))
             dfs2(s | (<<k-) , u | (<<k-) , cnt +  , k+);
         if(!(s & (<<k)) && !(u & (<<k-)))
             dfs2(s | (<<k) , u | (<<k-) , cnt +  , k+);
     }
     dfs2(s,u,cnt,k+);
 }
 int main()
 {
    // freopen("a.in","rb",stdin);
     while(~scanf("%d%d",&n,&m)){
         memset(dp,-,sizeof(dp));         if(n == ){
             puts("");
             continue;
         }         dfs2(,,,);         for(int i =  ; i<=n ; i++){
             for(int j =  ; j < <<m; j++){
                 for(int t =  ; t<<<m ; t++){
                     if(dp[i-][t][j]>=){
                         dfs(,j,t,dp[i-][t][j],,i);
                     }
                 }
             }
         }         int ans = ;
         for(int i =  ; i<<<m ; i++){
             for(int j =  ; j<<<m ; j++)
             {
                 //cout<<"in: "<<i<<" "<<" "<<j<<" "<<dp[n][i][j]<<endl;
                 ans = max(ans , dp[n][i][j]);
             }
         }
         printf("%d\n" , ans);
     }
     return ;
 }