状态压缩DP ， 和HDU2280极其相似
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 " , ans); 79 } 80 return 0; 81 }