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

POJ2411

《算法竞赛进阶指南》P298 状态压缩DP例题

所谓状态压缩DP,就是通过二进制数来记录状态集合,这个二进制数作为DP的维度。

#include<iostream>
using namespace std;
typedef long long ll;

int n,m;
ll f[12][1<<11];
bool in_s[1<<11];

int main(){
    while(cin>>n>>m&&n){
        for(int i=0;i<1<<m;++i){
            bool cnt=0,has_odd=0;//has_odd:已经出现一段奇数个连续的0,cnt:当前是否出现了奇数个0
            for(int j=0;j<m;++j){
                if(i>>j&1) has_odd|=cnt,cnt=0;
                else cnt^=1;
            }
            in_s[i]=has_odd|cnt?0:1;
        }
        f[0][0]=1;
        for(int i=1;i<=n;++i){
            for(int j=0;j<1<<m;++j){
                f[i][j]=0;
                for(int k=0;k<1<<m;++k){
                    if((j&k)==0&&in_s[j|k]){
                        f[i][j]+=f[i-1][k];
                    }
                }
            }
        }
        cout<<f[n][0]<<endl;

    }
    return 0;
}