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 can‘t be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

    Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

Input

 Line 1: Two space-separated integers: M and N

    Lines 2..M+1: Line i+1 describes row i of the pasture with N space-separated integers indicating whether a square is fertile (1 for fertile, 0 for infertile)

Output

Line 1: One integer: the number of ways that FJ can choose the squares modulo 100,000,000.

Sample Input

 2 3

 1 1 1

 0 1 0

Sample Output

9

Hint

Number the squares as follows:

    1 2 3

    4

    There are four ways to plant only on one squares (1, 2, 3, or 4), three ways to plant on two squares (13, 14, or 34), 1 way to plant on three squares (134), and one way to plant on no squares. 4+3+1+1=9.

Source

USACO 2006 November Gold

题意:给出一个n行m列的草地,1表示肥沃,0表示贫瘠,现在要把一些牛放在肥沃的草地上,但是要求所有牛不能相邻,问你有多少种放法。

分析:假如我们知道第 i-1 行的所有的可以放的情况,那么对于第 i 行的可以放的一种情况,我们只要判断它和 i - 1 行的所有情况的能不能满足题目的所有牛不相邻,如果有种中满足,那么对于 i 行的这一中情况有 x 中放法。

前面分析可知满足子状态,我们我们确定可以用dp来解决。

但是我们又发现,状态是一种放法,不是我们平常dp的简单的状态,所以要用状态压缩!

但是什么是状态压缩呢?

比如前面的情况,一种放法是最多由12个 0 或者 1 组成的,那么我们很容易想到用二进制,用二进制的一个数来表示一种放法。

定义状态dp【i】【j】,第 i 行状态为 j 的时候放牛的种数。j 的话我们转化成二进制,从低位到高位依次 1 表示放牛0表示没有放牛,就可以表示一行所有的情况。

那么转移方程 dp【i】【j】=sum(dp【i-1】【k】)

状态压缩dp关键是处理好位运算。

这个题目用到了 & 这个运算符。

用 x & (x<<1)来判断一个数相邻两位是不是同时为1,假如同时为 1 则返回一个值,否则返回 0 ,这样就能优化掉一些状态

用 x & y 的布尔值来判断相同为是不是同时为1。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define N 16
 6 #define M 1<<N
 7 #define MOD 100000000
 8 int mp[M];//记录每一行中,不能种植的就将状态记为1
 9 int state[M];//记录1<<m中不与别的数相邻的所有状态
10 int dp[N][M];
11 bool judge(int x){
12     return x&(x<<1);
13 }
14 bool judge2(int i,int j){
15     return mp[i]&state[j];
16 }
17 int main()
18 {
19     int n,m;
20     while(scanf("%d%d",&n,&m)==2){
21
22         memset(mp,0,sizeof(mp));
23         memset(state,0,sizeof(state));
24         memset(dp,0,sizeof(dp));
25
26         for(int i=1;i<=n;i++){
27             for(int j=1;j<=m;j++){
28                 int x;
29                 scanf("%d",&x);
30                 if(x==0){
31                     mp[i]+=(1<<(j-1));
32                 }
33             }
34         }
35
36         int k=0;
37         for(int i=0;i<(1<<m);i++){
38             if(judge(i)==0){
39                 state[k++]=i;
40             }
41         }
42
43         for(int i=0;i<k;i++){
44             if(judge2(1,i)==0){
45                 dp[1][i]=1;
46             }
47         }
48
49         for(int i=2;i<=n;i++){
50             for(int j=0;j<k;j++){
51                 if(judge2(i,j)) continue;
52                 for(int l=0;l<k;l++){
53                     if(judge2(i-1,l)) continue;
54                     if((state[j]&state[l])==0){
55                         dp[i][j]+=dp[i-1][l];
56                     }
57                 }
58             }
59         }
60         int ans=0;
61         for(int i=0;i<k;i++){
62             ans=ans+dp[n][i];
63             ans%=MOD;
64         }
65         printf("%d\n",ans);
66     }
67     return 0;
68 }

时间: 08-27

poj 3254 Corn Fields(状态压缩dp)的相关文章

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

题目链接: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: 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 (入门级)

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

[ACM] POJ 3254 Corn Fields(状态压缩)

Corn Fields Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 8062   Accepted: 4295 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 (状态压缩入门)

http://poj.org/problem?id=3254 参考:http://blog.csdn.net/accry/article/details/6607703 农夫想在m*n的土地上种玉米,但是有的土地很贫瘠,所以不能种,每块土地标为1的表示能种,标为0的表示不能种,并且种玉米的土地不能相邻, 问有多少种合法的种植方案.(全部不种也算一种) 第一道状压,理解了比较久的时间. 就是用二进制的0和1代表土地种还是不种,这样每一行都可以用一个2进制数表示,列数<=12,故最多有2<<

poj 3254 Corn Fields 国家压缩dp

意甲冠军: 要在m行n陆行,有一些格您可以种树,别人做不到的.不相邻的树,我问了一些不同的共同拥有的法律. 分析: 从后往前种,子问题向父问题扩展,当种到某一格时仅仅有他和他后面的n-1个格子的情况对它有影响.故对这n个格子进行编码为状态S,表示种完(多米诺骨牌那题是放置前.注意差别,都可行)这n个格子的状态.父问题由稍小子问题逐步解决,正是动态规划的思想. 代码: //poj 3254 //sep9 #include <iostream> using namespace std; const

Poj 3254 Corn Fields(状态压缩)

Corn Fields Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 8291   Accepted: 4409 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 Field ( 状态压缩DP )

简单题,边界处理注意.可以优化,就不精益求精了. #include <iostream> #include <cstring> #include <vector> #include <fstream> using namespace std; #define MOD 100000000 int field[20]; int DP[20][1200]; int main(){ int N, M; cin >> N >> M; memse

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.