poj3254--Fields+状态压缩dp

第一道状态压缩dp :)

考虑每一行的情况,如果我们令0表示不可以放牧1表示放牧,那么这一行所有可行的情况都可以穷举出来并对应到一个十进制的数;这就是状态压缩。再由题目可以知道每一行的状态可不可以出现只和它前面的那一行有关,所以我们可以定义 dp[i][j]表示第i行处于第j种状态的时候有多少种放牧的方法;

dp[i][j]=dp[i-1][j1]+dp[i-1][j2]+。。。。+dp[i-1][jn],其中j要和jn能同时出现。

由这个方程我们就可以写程序了,我们可以选择用一个数组来表示状态然后进行相应的判断,但是我们可以通过位运算更方便的实现这些判断。

首先我们不需要把穷举每个状态,我们可以通过题目限制条件(两个1不能相邻)先筛选出所有合法的状态,这个操作用x&(x<<1)进行判断,如果为0则表示无相邻否则相反;然后我们还要判断这些合法状态是否和是否和初始状态冲突,这时我们需要将初始状态01取反,0变成1,1变成0(这样只需要判断如果与原状态1位置上对应的状态是不是0,可以通过&实现),这样我们只需要将某个状态与其&,如果为1则表示不合法,为0则合法。最后我们需要判断对应两个数的二进制表示的相同位是否同时为1,这个也可以通过&实现。

这些操作都用位运算实现后,我们就可以方便的写出代码了。

代码如下

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define mod 1000000000
int total[1000];
int dp[15][1000];
int top;
int cur[15];
int n,m;

int ok(int i,int j)
{
    if(i&j)
       return 0;
    return 1;
}

void Allstate()
{
    top=1;
    int j=1<<m;
    for(int i=0;i<j;i++)
    {
        if(i&(i<<1))
          continue;
        total[top++]=i;
    }
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
         Allstate();
         memset(cur,0,sizeof(cur));
         for(int i=1;i<=n;i++)
         {
           for(int j=1;j<=m;j++)
           {
               int x;
               scanf("%d",&x);
               cur[i]=cur[i]*2+x;
           }
           cur[i]=~cur[i];//实现按位取反
         }
         memset(dp,0,sizeof(dp));
         for(int i=1;i<top;i++)
         {
             if(ok(cur[1],total[i]))
                dp[1][i]=1;
         }
         for(int i=2;i<=n;i++)
           for(int j=1;j<top;j++)
           {
               if(ok(cur[i],total[j]))
               {
                   for(int d=1;d<top;d++)
                   {
                       if(ok(total[d],total[j]))
                         dp[i][j]=(dp[i][j]+dp[i-1][d])%mod;
                   }
               }
           }
         int ans=0;
         for(int i=1;i<top;i++)
         {
             ans=(ans+dp[n][i])%mod;
         }
         printf("%d\n",ans);
    }
  return 0;
}
时间: 01-27

poj3254--Fields+状态压缩dp的相关文章

POJ3254 Corn Fields 状态压缩DP

题目大意是在一块M行N列的农场上种谷物,但是不希望彼此相邻(共用一条边),并且有些地方不能种植谷物,给定M,N(范围都不超过12)以及一些不能种谷物的位置,求出一共有多少种方法种谷物. 状态压缩DP,设dp(i, k) 为种到第i行时,第i行状态为k的总共方案数,可以知道dp(i, k) = ∑dp(i -1, k'),其中我们要判断彼此相邻的情况以及不能种植的情况即可. #include <stdio.h> #include <vector> #include <math.

POJ 3254 Corn Fields 状态压缩DP (C++/Java)

http://poj.org/problem?id=3254 题目大意: 一个农民有n行m列的地方,每个格子用1代表可以种草地,而0不可以.放牛只能在有草地的,但是相邻的草地不能同时放牛, 问总共有多少种方法. 思路: 状态压缩的DP. 可以用二进制数字来表示放牧情况并判断该状态是否满足条件. 这题的限制条件有两个: 1.草地限制. 2.相邻限制. 对于草地限制,因为输入的时候1是可以种草地的. 以"11110"草地分析,就只有最后一个是不可以种草的.取反后得00001  .(为啥取反

POJ 3254 Corn Fields(状态压缩DP)

Corn Fields Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 4739   Accepted: 2506 Description Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yumm

POJ 3254 Corn Fields 状态压缩DP

题目链接:http://poj.org/problem?id=3254 思路:状态压缩DP,状态方程为dp[i][j] += (dp[i-1][k]) code: #include <stdio.h> #include <string.h> #define N 500 const int MOD = 100000000; int dp[15][N],ant[N],n,m,k,map[15]; bool ok(int x) { if(x&(x<<1))return

POJ 3254. Corn Fields 状态压缩DP (入门级)

Corn Fields Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 9806   Accepted: 5185 Description Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yumm

状态压缩dp入门 (poj3254 Corn Fields)

题目链接:http://poj.org/problem?id=3254 题意:给出一个n行m列的草地,1表示肥沃,0表示贫瘠,现在要把一些牛放在肥沃的草地上,但是要求所有牛不能相邻,问你有多少种放法. 分析:假如我们知道第 i-1 行的所有的可以放的情况,那么对于第 i 行的可以放的一种情况,我们只要判断它和 i - 1 行的所有情况的能不能满足题目的所有牛不相邻,如果有种中满足,那么对于 i 行的这一中情况有 x 中放法. 前面分析可知满足子状态,我们我们确定可以用dp来解决. 但是我们又发现

POJ3254:Corn Fields(状态压缩)

Description Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and

poj 3254 Corn Fields ,状态压缩DP

题目链接 题意: 一个矩阵里有很多格子,每个格子有两种状态,可以放牧和不可以放牧,可以放牧用1表示,否则用0表示,在这块牧场放牛,要求两个相邻的方格不能同时放牛,即牛与牛不能相邻.问有多少种放牛方案(一头牛都不放也是一种方案) state[i] 表示对于一行,保证不相邻的方案 状态:dp[i][ state[j] ]  在状态为state[j]时,到第i行符合条件的可以放牛的方案数 状态转移:dp[i][ state[j] ] =Sigma dp[i-1][state'] (state'为符合条

状态压缩dp入门 第一题 POJ 3254 Corn Fields

Corn Fields Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 6460   Accepted: 3436 Description Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yumm

poj 3254 Corn Fields(状态压缩dp)

Description Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and