POJ 2411 Mondriaan's Dream (状压DP)

dp[i][j]表示第i行  为j 状态的有多少种方法。

就要写一个匹配的函数，保证上一行可以跟这一行凑出来合法的满满的两行。

也就是其他博客里说的。

1、如果第i行中有0，则第i-1行一定为1；

2、如果第i行中为1的x列第i-1行为0，说明第i行肯定是竖着放的；

3、如果第i行中为1的x列第i-1行的该列也为1，可能性只有一个，第i行是横放的，所以第i行的x+1列也必须为1，又因为第i行的x+1列为1是因为横着放的，所以第i-1行的x+1列也必须为1。

那么状态转移就很简单了。

dp[i][cur] += dp[i-1][last]  如果last和cur能匹配的话。

还有输出的时候为什么是输出dp[n][1<<m-1]   。

因为你在这一行是1 上一行是0    等同于这一行是0 上一行是 1

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;

LL dp[11][1<<11];
int n,m;

bool ok(int x)
{
    int pos=1;
    int count=0;
    for(int i=0;i<(1<<m);i++,pos<<=1)
    {
        if(x&pos)count++;
        else
        {
            if(count&1)return false;
            else count=0;
        }
    }
    return !(count&1);
}
bool match(int last,int cur)
{
    for(int pos=1;pos<(1<<m);)
    {
        if(!(last&pos) && !(cur&pos))return false;
        else if((last&pos)&&(cur&pos))
        {
            if(((pos<<1)&last) && ((pos<<1)&cur))pos<<=2;
            else return false;
        }
        else pos<<=1;
    }
    return true;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF && n && m)
    {
        if(n<m)swap(n,m);

        memset(dp,0,sizeof dp);

        for(int i=0;i<(1<<m);i++)
        {
            if(ok(i))dp[0][i]=1;
        }

        for(int i=1;i<n;i++)
        {
            for(int last=0;last<1<<m;last++)
            {
                for(int cur=0;cur<1<<m;cur++)
                if(match(last,cur))
                dp[i][cur]+=dp[i-1][last];
            }
        }
        cout<<dp[n-1][(1<<m)-1]<<endl;
    }
    return 0;
}

POJ 2411 Mondriaan's Dream (状压DP)

原文：http://blog.csdn.net/u010709592/article/details/19178021