luogu P1879 [USACO06NOV]玉米田Corn Fields

分析：

第一眼就知道是个水的不要不要的压状dp的题目，秒切。0ms毫不压力过（预处理合法状态）。

#include<bits/stdc++.h>
using namespace std;
const int maxn=15;
typedef long long ll;
int cnt=0;
const ll MOD=100000000;
ll f[maxn][1<<15],p[1<<15],n,m;//f(i,j)当防止第i行时，上行状态为j时的方案 p记录合法状态 
bool book[maxn][maxn];
//判断没有相邻的草地 
bool pd(int a){
    bool re=0;
    while(a>0){
        if(a&1&&re)return 0;
        re=a&1;
        a>>=1; 
    }
    return 1;
}
//判断是否在草地上 
bool pd2(int n,int a){
    int t=m;
    while(a>0){
        if((a&1)&&!book[n][t])return 0;
        --t;
        a>>=1;
    }
    return 1;
}
void init(){
    cin>>n>>m;
    for(int i=0;i<(1<<m);++i){  //统计合法状态 
        if(pd(i)){
            p[++cnt]=i;
        }
    }
    for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)cin>>book[i][j];
}

void solve(){
    f[0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=cnt;++j){
            for(int k=1;k<=cnt;++k){
                if(pd2(i,p[k])&&!(p[k]&p[j])){
                    f[i][p[k]]=(f[i][p[k]]+f[i-1][p[j]])%MOD;
                }
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=cnt;++i){
        ans+=f[n][p[i]];
        ans%=MOD; 
    }
    cout<<ans;
}
int main(){
    init(); 
    solve();
    return 0;
}