poj 2411 状态压缩dp

横的看成11，竖的看成0/1，

1.相邻2行之间是否冲突就是看a|b是否全是1。

2.同一行是否冲突就是看横着的1的个数是否是奇数。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
long long dp[15][1<<12];
int ok[1<<12];
bool isok(int sta)
{
    int tot=0;
    while(sta)
    {
        if(sta&1)
        {
            tot++;
            sta>>=1;
            if(sta&1) {sta>>=1;tot++;}
            else return false;
        }
        else sta>>=1;
    }
    return !(tot&1);
}
int main()
{
    int n,m;
    int top=(1<<11)-1;
    for(int i=0;i<=top;i++) ok[i]=isok(i);
    while(~scanf("%d%d",&n,&m)&&(n||m))
    {
        top=(1<<m)-1;
        memset(dp,0,sizeof(dp));
        for(int i=0;i<=top;i++) if(ok[i]) dp[1][i]=1;
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<=top;j++)
            {
                for(int k=0;k<=top;k++)
                {
                    if((k|j)==top&&ok[k&j]) dp[i][j]+=dp[i-1][k];
                }
            }
        }
        cout<<dp[n][top]<<endl;
    }
    return 0;
}

poj 2411 状态压缩dp

原文：http://blog.csdn.net/t1019256391/article/details/18376521