poj1741，POJ 3254 poj3254 Corn Fields

題意：給出一個n行m列的草地，1表示肥沃，0表示貧瘠，現在要把一些牛放在肥沃的草地上，但是要求所有牛不能相鄰，問你有多少種放法。

思路：

DP[i][j]=sum(dp[i-1][k]); i表示當前這一行，狀態為j有多少種方案

poj1741。首先，i行能放牛的狀態由前一行i-1決定。所以我們只要知道前一行的狀態就知道這一行的方案。因此要初始化第一行的狀態dp[1][i]

要使當前這一行能用狀態j表示則應瞞足兩種條件

1 與當前這一行的地形符合

2 這一行狀態與前一行的某一狀態不沖突

poj2352。x&(x<<1)表示x的二進制是否有兩個相鄰的1相鄰

注意，初始化地形狀態的時候，應該是0所在的位所構成的數

//#pragma comment(linker, "/STACK:167772160")//手動擴棧~~~~hdu 用c++交
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <algorithm>
#include <vector>
// #include<malloc.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define LL long long
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const double pi = acos(-1);
const LL MOD = 1e8;
const int N=1<<13;
// const LL p = 1e9+7;
// inline int r(){
//     int x=0,f=1;char ch=getchar();
//     while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
//     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
//     return x*f;
// }

int dp[15][N];
int G[N];
int line[N];
bool judge1(int x){
    return (x&(x<<1));
}

bool judge2(int x,int y){
    return G[x]&line[y];
}
int main(){
    int m,n;
    while(~scanf("%d%d",&n,&m)){
        // clc(G,0);
        // clc(dp,0);
        // clc(line,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int x;
            scanf("%d",&x);
            if(x==0){
               G[i]+=(1<<(m-j));
            }
        }
    }

    int k=0;
    for(int i=0;i<(1<<m);i++){
        if(!judge1(i)){
            line[k++]=i;
        }
    }
    for(int i=0;i<k;i++){
        if(!judge2(1,i))
            dp[1][i]=1;
    }

    for(int i=2;i<=n;i++){
        for(int j=0;j<k;j++){
            if(judge2(i,j))
                continue;
            for(int f=0;f<k;f++){
                if(judge2(i-1,f))
                    continue;
                if(!(line[j]&line[f]))
                    dp[i][j]+=dp[i-1][f];
            }
        }
    }
    
    int ans=0;
    for(int i=0;i<k;i++){
        ans+=dp[n][i];
        ans%=MOD;
    }
    printf("%d\n",ans);
    }
    return 0;
}

?