首页 > 其他 > 详细

Corn Fields - POJ 3254(状态压缩)

时间:2015-10-03 18:08:21      阅读:217      评论:0      收藏:0      [点我收藏+]

题目大意:有一个M*N的牧场,G(i, j) = 1表示这块地营养丰富,可以喂养牛,等于0表示贫瘠,不能喂养牛,所有的牛都讨厌与别的牛相邻,求有多少种放置牛的方式。

分析:算是炮兵那个题的弱化版吧,先求出来所有的合法状态(不到500种),然后与上一行的状态匹配即可。

代码如下:

===============================================================================================================================

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;

const int MAX_N = 1<<12;
const int MAX_M = 13;
const int Mod = 1e8;

int dp[MAX_M][MAX_N];
int bit[1<<12], cnt, M, N;

void DFS(int layer, int state)
{
    if(layer >= N)
    {
        bit[cnt++] = state;
        return ;
    }
    DFS(layer+1, state);
    DFS(layer+2, state|(1<<layer));
}

int main()
{
    while(scanf("%d%d", &M, &N) != EOF)
    {
        int x, data[MAX_M]={0};

        cnt = 0;
        DFS(0, 0);

        for(int i=1; i<=M; i++)
        for(int j=0; j<N; j++)
        {
            scanf("%d", &x);
            data[i] = data[i] * 2 + (x^1);
        }

        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;

        for(int t=1; t<=M; t++)
        {
            for(int i=0; i<cnt; i++)if(!(data[t] & bit[i]))
            for(int j=0; j<cnt; j++)if(!(data[t-1]&bit[j]))
            {
                if(!(bit[i] & bit[j]))
                {
                    dp[t][i] += dp[t-1][j];
                    dp[t][i] %= Mod;
                }
            }
        }

        int ans = 0;

        for(int i=0; i<cnt; i++)
            ans = (ans+dp[M][i]) % Mod;

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

    return 0;
}

 

Corn Fields - POJ 3254(状态压缩)

原文:http://www.cnblogs.com/liuxin13/p/4853650.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!