POJ - 3254 Corn Fields（状压DP）题解

思路：

参照blog，用状压DP做，和题解稍微有点不一样，我这里直接储存了状态而不是索引。

这一题的问题是怎么判断相邻不能种，我们用2进制来表示每一行的种植情况。我们将每一行所能够造的所有可能都打表（即认为每一块都能种），然后将每一行不能种的地方用2进制保存下来，两者&运算聚能知道是否有重合，重合即此方法排除；上下两行同理；判断左右两块则是左移后&运算。

状态DP做的时候想着2进制时候的表示会好做点

代码：

#include<cstdio>

#include<map>

#include<set>

#include<queue>

#include<cstring>

#include<string>

#include<cmath>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

const int N = 500+5;

const int MOD = 100000000;

const int INF = 0x3f3f3f3f;

using namespace std;

int n,m,top;

ll dp[15][1<<12+5];

int state[600],cur[15];

void init(){    //所有可能状态

    top = 0;

    int tot = 1 << n;

    for(int i = 0;i < tot;i++){

        if(i&i<<1) continue;

        state[++top] = i;

    }

}

int main(){

    scanf("%d%d",&m,&n);

    init();

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

    for(int i = 1;i <= m;i++){

        int tmp;

        cur[i] = 0;

        for(int j = 1;j <= n;j++){

            scanf("%d",&tmp);

            if(tmp == 0){

                cur[i] += 1<<(n - j);   //记录每一行不能种的

            }

        }

    }

    for(int i = 1;i <= top;i++){

        if(cur[1]&state[i]) continue;   //冲突

        dp[1][state[i]] = 1;

    }

    for(int i = 2;i <= m;i++){  //第i行

        for(int j = 1;j <= top;j++){    //i状态

            if(cur[i]&state[j]) continue;

            for(int k = 1;k <= top;k++){    //i-1状态

                if(state[k]&cur[i-1]) continue;

                if(state[j]&state[k]) continue;

                dp[i][state[j]] += dp[i - 1][state[k]];

            }

        }

    }

    ll ans = 0;

    for(int i = 1;i <= top;i++){

        ans += dp[m][state[i]];

        ans %= MOD;

    }

    printf("%lld\n",ans % MOD);

    return 0;

}

巴特西

POJ - 3254 Corn Fields（状压DP）题解

最新文章

热门文章