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;
}