【poj 3254】Corn Fields題意＆題解＆コード(C＋＋)

タイトルリンク:http://poj.org/problem?id=3254 标题:n行m列の草地を与え、1は肥沃、0はやせこけ、今は任意の数の牛を肥沃な草地に置くが、すべての牛が隣接できないことを要求し、どれだけの放法があるかを聞く.問題解:状態圧縮型dpは、一般的にデータ範囲で判断でき、各行の肥沃な芝生状態と牛の分布状態をバイナリ数で表すことができ、dp[i][j]はi行目の牛の状態がjの方法数であることを示し、移行方法はコードを参照し、2つの牛が隣接できないことを見出した.ではバイナリ状態種には多くの状態が満たされていないという性質があり,本来2^m種の状態が前処理された後に実際に満たされている制限の状態数が少なく,自分で小さなプログラムを書いて最大何種類あるかを計算することができる.コード:

#include
#include
#include
using namespace std;
int ans,n,m,dp[13][1<<13],map[13],st[1<<13];
int M=1e8;
int judge1(int x)//            
{
    return x&(x<<1);
}
int judge2(int i,int x)//            
{
    return map[i]&x;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
    {
        int x;
        scanf("%d",&x);
        if (x==0) map[i]+=(1<1));
    }
    int tot=0;
    for (int i=0;i<=(1<1;i++)
    if (!judge1(i))
    {
        tot++;
        st[tot]=i;
    }
    for (int i=1;i<=tot;i++)
    {
        if (judge2(1,st[i])==0)
        dp[1][i]=1;
    }
    for (int i=2;i<=n;i++)
    {
        for (int j=1;j<=tot;j++)
        {
            if (judge2(i,st[j])) continue;
            for (int k=1;k<=tot;k++)
            {
                if (judge2(i-1,st[k])) continue;
                if ((st[j]&st[k])==0)
                {
                    dp[i][j]+=dp[i-1][k];
                    dp[i][j]%=M;
                }
            }       
        }
    }
    for (int i=1;i<=tot;i++)
    {
        ans+=dp[n][i];
        ans%=M;
    }
    printf("%d
",ans);
}