CDOJ885（插頭dp，狀态壓縮）

題意為給一個n*m的棋盤，有兩種木塊，1*2的和2*1的，求将整個棋盤放滿有多少種方案。

n,m都是 小于12的。可以用插頭dp來求解，定義狀态1表示目前格子有插頭，0表示沒有插頭。顯然每個格子隻能而且必須有1格插頭，那麼狀态的轉移：

目前格子的插頭狀态為00,則由上一狀态的00，01，10轉移而來；

目前格子的插頭狀态為01，或者10，則由上一狀态的00轉移過來；

目前格子的插頭狀态為11，則dp值為0（一個格子不能有兩個插頭）。

代碼如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
long long dp[12][12][4200];
int main() {
    while (~scanf("%d%d",&n,&m)) {
        int all=1<<(m+1);
        memset(dp,0,sizeof(dp));
        dp[0][m][0]=1;
        for (int i=1; i<=n; i++) {
            for (int k=0; k<(all>>1); k++) dp[i][0][k<<1]=dp[i-1][m][k];
            for (int j=1; j<=m; j++) {
                for (int k=0; k<all; k++) {
                    int x=1<<(j-1);
                    int y=1<<j;
                    if ((x&k)&&(y&k)) dp[i][j][k]=0;                    //兩個插頭
                    else if ((x&k)||(y&k)) {                            //一個插頭
                        int z=x|y;
                        dp[i][j][k]=dp[i][j-1][k&(~z)];
                    } else dp[i][j][k]=dp[i][j-1][k|x]+dp[i][j-1][k|y]; //沒有插頭
                }
            }
        }
        printf("%lld\n",dp[n][m][0]);
    }
    return 0;
}
           

還有一種用狀态壓縮的寫法，相對來說比較麻煩，代碼：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int h,w,tot;
long long dp[12][2050];
long long dfs(int x,int now,int pre,int i) {
    if (now==0) {
        if (x==0) return 1;
        else return dp[x-1][tot-pre];
    }
    long long ans=0;
    if (now&(1<<i)) {
        if (x>0) ans+=dfs(x,now-(1<<i),pre+(1<<i),i+1);
        if (now&(1<<(i+1))) ans+=dfs(x,now-(1<<i)-(1<<(i+1)),pre,i+2);
    } else ans=dfs(x,now,pre,i+1);
    return ans;
}
int main() {
    while (~scanf("%d%d",&h,&w)) {
        memset(dp,0,sizeof(dp));
        tot=(1<<w)-1;
        for (int i=0; i<=h; i++)
            for (int j=0; j<=tot; j++)
                dp[i][j]+=dfs(i,j,0,0);
        printf("%lld\n",dp[h][0]);
    }
    return 0;
}