1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4  5 using namespace std; 6 const int N = 105; 7 int dp[N][1<<6][1<<6] , n , m; 8  9 //s 表示当前第i行的状态 , u表示上一行状态 , v表示上上行的状态 , cnt表示到当前位置时总共占据的空间10 void dfs(int s , int u , int v , int cnt , int k , int i) //由右到左，访问到第i行的第k位数字11 {12     if(k >= m){13         dp[i][u][s] = max(dp[i][u][s] , cnt);14         return;15     }16     if(k > 0){17         if(!(s & (1<<k)) && !(u & (3<<k-1)) && !(v & (1<<k)))18             dfs(s | (1<<k) , u | (3<<k-1) , v | (1<<k) , cnt + 4 , k+1 , i);19         if(!(s & (1<<k)) && !(u & (1<<k)) && !(v & (3<<k-1)))20             dfs(s | (1<<k) , u | (1<<k) , v | (3<<k-1) , cnt + 4 , k+1 , i);21     }22     if(k > 1){23         if(!(s & (1<<k-1)) && !(u & (7<<k-2)) && !(v & (1<<k-1)))24             dfs(s | (1<<k-1) , u | (7<<k-2) , v | (1<<k-1) , cnt + 5 , k+1 , i);25         if(!(s & (1<<k-1)) && !(u & (7<<k-2)))26             dfs(s | (1<<k-1) , u | (7<<k-2) , v , cnt + 4 , k+1 , i);27         if(!(s & (1<<k)) && !(u & (7<<k-2)))28             dfs(s | (1<<k) , u | (7<<k-2) , v , cnt + 4 , k+1 , i);29     }30     dfs(s, u , v , cnt , k+1 , i);31 }32 33 void dfs2(int s , int u , int cnt , int k)34 {35     if(k >= m){36         dp[2][u][s] = max(dp[2][u][s] , cnt);37         return;38     }39     if(k > 1){40         if(!(s & (1<<k-1)) && !(u & (7<<k-2)))41             dfs2(s | (1<<k-1) , u | (7<<k-2) , cnt + 4 , k+2);42         if(!(s & (1<<k)) && !(u & (7<<k-2)))43             dfs2(s | (1<<k) , u | (7<<k-2) , cnt + 4 , k+1);44     }45     dfs2(s,u,cnt,k+1);46 }47 int main()48 {49     freopen("a.in","rb",stdin);50     while(~scanf("%d%d",&n,&m)){51         memset(dp,-1,sizeof(dp));52 53         if(n == 1){54             puts("0");55             continue;56         }57 58         dfs2(0,0,0,0);59 60         for(int i = 3 ; i<=n ; i++){61             for(int j = 0 ; j < 1<<m; j++){62                 for(int t = 0 ; t<1<<m ; t++){63                     if(dp[i-1][t][j]>=0){64                         dfs(0,j,t,dp[i-1][t][j],0,i);65                     }66                 }67             }68         }69 70         int ans = 0;71         for(int i = 0 ; i<1<<m ; i++){72             for(int j = 0 ; j<1<<m ; j++)73             {74                 //cout<<"in: "<<i<<" "<<" "<<j<<" "<<dp[n][i][j]<<endl;75                 ans = max(ans , dp[n][i][j]);76             }77         }78         printf("%d\n" , ans);79     }80     return 0;81 }