poj 2411 新寫法

今天做了場srm，500pt想到了是dp但是無從下手，但是看了rng_58的神代碼後頓覺海闊天空啊（盯著看了一個下午），相比於一年前的寫法，真的是不忍直視啊，

TC真是個好地方。。。贊！

其實就是將普通的鋪磚塊問題用類似於插頭dp逐格遞推的思路來寫。下面的代碼相信大家應該都能看懂。

#include <cstdio>  
#include <cstring>  
#include <algorithm>  
long long dp[2][1<<11]; 
int main() { 
    int n , m; 
    while(scanf("%d%d",&n,&m),n||m) { 
      int cur = 0 , nxt = 1; 
      dp[cur][0] =  1; 
       for(int i = 0; i < n; i++) { 
          for(int j = 0; j < m; j++) { 
            memset(dp[nxt],0,sizeof(dp[nxt])); 
            for(int s = 0; s < (1<<m); s++) if(dp[cur][s]){ 
                if(s&1){dp[nxt][s>>1] += dp[cur][s];continue;} 
                if(j+1<m && !(s&2) ){ 
                    int mask = ( s | 2 ) >> 1; 
                    dp[nxt][mask] += dp[cur][s]; 
                } 
                if(i+1<n) { 
                    int mask = (s | (1<<m)) >> 1; 
                    dp[nxt][mask] += dp[cur][s]; 
                } 
            } 
            std::swap(cur,nxt); 
          } 
       } 
       printf("%I64d\n",dp[cur][0]); 
    } 
    return 0; 
} 

#include <cstdio>
#include <cstring>
#include <algorithm>
long long dp[2][1<<11];
int main() {
    int n , m;
    while(scanf("%d%d",&n,&m),n||m) {
      int cur = 0 , nxt = 1;
      dp[cur][0] =  1;
       for(int i = 0; i < n; i++) {
          for(int j = 0; j < m; j++) {
            memset(dp[nxt],0,sizeof(dp[nxt]));
            for(int s = 0; s < (1<<m); s++) if(dp[cur][s]){
                if(s&1){dp[nxt][s>>1] += dp[cur][s];continue;}
                if(j+1<m && !(s&2) ){
                    int mask = ( s | 2 ) >> 1;
                    dp[nxt][mask] += dp[cur][s];
                }
                if(i+1<n) {
                    int mask = (s | (1<<m)) >> 1;
                    dp[nxt][mask] += dp[cur][s];
                }
            }
            std::swap(cur,nxt);
          }
       }
       printf("%I64d\n",dp[cur][0]);
    }
    return 0;
}

下面是一年前的寫法。。。

#include<stdio.h>  
#include<string.h>  
int h,w; 
__int64 dp[15][2050]; 
void dfs1(int row,int state,int col,int state2){ 
    if(col>w) return ; 
    if(col==w) { 
        dp[row+1][state2]+=dp[row][state]; 
        return ; 
    } 
    if(!(state&(1<<col))) dfs1(row,state,col+1,state2+(1<<col)); 
    else dfs1(row,state,col+1,state2); 
} 
void dfs2(int row,int state,int col,int state2){ 
    if(col>w) return ; 
    if(col==w) { 
        if(state2!=state)   
           dp[row][state2]+=dp[row][state]; 
        return ; 
    } 
    if(!(state&(1<<col)) &&   !(state&(1<<(col+1)))) 
        dfs2(row,state,col+2,state2+(1<<col) + (1<<(col+1))); 
    dfs2(row,state,col+1,state2); 
} 
void gao(){ 
    int i,j; 
    dp[0][(1<<w)-1]=1; 
    for(i=0;i<h;i++){ 
          for(j=0;j<(1<<w);j++) 
              if(dp[i][j]) 
                  dfs1(i,j,0,0); 
          for(j=(1<<w)-1;j>=0;j--) 
              if(dp[i+1][j]) 
                  dfs2(i+1,j,0,j); 
    } 
} 
int main(){ 
    while(scanf("%d%d",&h,&w)!=EOF && h+w){ 
        int temp; 
        if(h<w){ 
            temp=h;h=w;w=temp; 
        } 
        memset(dp,0,sizeof(dp)); 
        gao(); 
        printf("%I64d\n",dp[h][(1<<w)-1]); 
    } 
    return 0; 
}