Hua Rong Dao [FZU 2107] 状态压缩DP模板

http://acm.fzu.edu.cn/problem.php?pid=2107

状态压缩DP，dp[i][j][k] 表示前i行j状态，有没有2*2

普通放板的问题。深搜枚举的过程中记录当前和转移到的状态。

const int MM = 1111;
typedef __int64 int64;
#define debug puts("wrong")
int N,M,L,ans,ss;
char str[MM];
int num[MM];
int dp[10][32][3]; //0 no 1 yes
void get_data() {
    int i,j,k;
    scanf("%d",&N);
}
void dfs(int row,int pre,int cao,int col,int now) {  //row行数 pre前一行状态数 col列数 now当前行状态 
    if(cao>2)  return;
    if(col>=4) {
         dp[row][now][cao] += ss;
        return;
    }
    
    if((pre>>col)&1) {
         dfs(row,pre,cao,col+1,now);
    }
     else {
        dfs(row,pre|(1<<col),cao,col+1,now|(1<<col));
           dfs(row,pre|(1<<col),cao,col+1,now);
           
         if(col<3 && ((pre>>(col+1))&1)==0)  {
               dfs(row,pre|(1<<col)|(1<<(col+1)),cao,col+1,now);
               int tmp=(1<<col)|(1<<(col+1));
              if(cao==0) dfs(row,pre|tmp,cao+1,col+1,now|tmp);
           }
     }
}

void solve() {
    int i,j,k,state=(1<<4)-1;
    memset(dp,0,sizeof(dp));
    dp[0][state][0]=1; 
    for(i=1;i<=N+1;i++) {
        for(j=0;j<=state;j++) {
            if(dp[i-1][j][0]==0)  continue; 
            ss=dp[i-1][j][0];
            dfs(i,j,0,0,0);
            
            if(dp[i-1][j][1]==0)  continue; 
            ss=dp[i-1][j][1];
            dfs(i,j,1,0,0);
        }
    }
    printf("%d\n",dp[N+1][0][1]);
}
int main() {
    int ca; scanf("%d",&ca);
    while(ca--) get_data(),solve();
    return 0;
}