Mondriaan's Dream(POJ 2411状态压缩dp)

时间：2022-10-13 08:12:56

题意:用1*2的方格填充m*n的方格不能重叠，问有多少种填充方法

分析：dp[i][j]表示i行状态为j时的方案数，对于j,0表示该列竖放（影响下一行的该列），1表示横放成功（影响下一列）或上一列竖放成功。状态转移时，枚举每一行可能的状态上一行取反得下一行能放的状态。

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<11

#define All 1,N,1

#define read freopen("in.txt", "r", stdin)

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0x7ffffff;

const int mod =  1000000007;

int n,m;

ll dp[15][1<<11],x;

//枚举可能的状态

void dfs(int i,int j,int p){

    if(p==m){

        dp[i][j]+=x;

        return;

    }

    dfs(i,j,p+1);

    if(p+2<=m&&!(j&(1<<p))&&!(j&(1<<(p+1))))

    dfs(i,(j|(1<<p)|(1<<(p+1))),p+2);

}

void solve(){

    memset(dp,0,sizeof(dp));

    x=1;

    dfs(1,0,0);

    ll cas=(1<<m);

//x为上一行可能的方案总数

    for(int i=2;i<=n;++i){

        for(int j=0;j<cas;++j){

            if(dp[i-1][j]){

            x=dp[i-1][j];

            dfs(i,~j&(cas-1),0);

            }

        }

    }

    printf("%I64d\n",dp[n][cas-1]);

}

int main()

{

    while(~scanf("%d%d",&n,&m)){

        if(n==0&&m==0)break;

        solve();

    }

return 0;

}

　　

相关文章