poj 3254(状态压缩+动态规划)

题意：有一个n*m的农场（01矩阵），其中1表示种了草可以放牛，0表示没种草不能放牛，并且如果某个地方放了牛，它的上下左右四个方向都不能放其他的牛，

问总共有多少种放牛方案？？（不放也是一种方案）

分析：利用状态压缩进行求解，先筛选出每行所有的可能状态，然后将每行与所有可行状态进行比较。

dp[i][j]表示当第i行的状态为j时前i行的放牛方案总数。

所以状态转移方程便是 dp[i][j] = dp[i][j]+dp[i-1][t] //t代表第i-1行所有符合条件的状态数。

最后的结果为 sum(dp[n][i]) ..数组开小了，不停WA

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#define N 12

#define mod 100000000

using namespace std;

int dp[N+][<<N];  ///dp[i][j]表示当第i行的状态为j时前i行的放牛方案总数

int state[<<N]; ///保存所有的合法状态数

int cur[N+]; ///每一行的状态,注意这里保存的是0,因为当我们保存0时,如果某一状态与当前行相与不为0，那么

///就能判断出那个状态是不合法的(假设那个位置不应该种草，而它种了草)

int n,m;

bool check(int k){

    if(k&(k<<)) return false;

    return true;

}

void init(int &k){

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

        if(check(i)) state[++k]=i;

    }

    //printf("%d\n",k);

}

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF){

        int k = ;

        init(k);

        int num;

        memset(dp,,sizeof(dp));

        for(int i=;i<=n;i++){

            cur[i]=;

            for(int j=;j<=m;j++){

                scanf("%d",&num);

                if(num==) cur[i]+=(<<(j-));

            }

        }

        for(int i=;i<=k;i++){

            if(!(cur[]&state[i])){

                dp[][i]=;

            }

        }

        for(int i=;i<=n;i++){

            for(int j=;j<=k;j++){

                if(cur[i]&state[j]) continue; ///枚举第i行的可行状态state[j]

                for(int t = ;t<=k;t++){

                    if(cur[i-]&state[t]) continue; ///枚举第i-1行的可行状态state[t]

                    if(state[j]&state[t]) continue; ///判断相邻两行状态是否合法

                    dp[i][j] = (dp[i][j]+dp[i-][t]+mod)%mod;

                }

            }

        }

        int ans = ;

        for(int i=;i<=k;i++){

            ans = (ans+dp[n][i]+mod)%mod;

        }

        printf("%d\n",ans);

    }

    return ;

}

秒客网

poj 3254(状态压缩+动态规划)

相关文章