题解 P1879 【[USACO06NOV]玉米田Corn Fields】

· · 题解

一道明显的状压dp

首先用位运算 | 将每一行的信息存进mp里； 对第一行单独初始化，后依次枚举本行状态和上一行的状态，枚举每种状态时记得除去不可行解

采用位运算判断无疑是最快的

j & j-1 可以快速判断是否有两个以上连续的1；

( mp [ i ] | l ) == mp [ i ] ; 可以判断是否在地图上是0的位置种草了，如果mp[i]中有一位是1，那么无论l (l为当前行状态）的这一位是什么都不会改变，而当mp[i]中某位为0时，如果l状态的当前位置为1（种草）则会改变mp[i]的值；

附上菜鸡代码

#include<bits/stdc++.h>
using namespace std;
int n,m,sum=0,mod=1e9;
int mp[105]={0},dp[13][1<<12];//mp存储地图情况，dp枚举每一种状况
int main(){
    cin>>m>>n;
    for(int i=1;i<=m;i++)
        for(int j=0;j<n;j++){
            int x;
            cin>>x;
            mp[i]|=(x<<j);//记录地图信息
        }
    for(int l=0;l<(1<<n);l++){
        if((l&(l>>1)))  continue;   
        if((mp[1]|l)!=mp[1])    continue;
        dp[1][l]=1; 
    }//初始化第一行的情况
    for(int i=2;i<=m;i++){
        for(int j=0;j<(1<<n);j++){//当前行 
            int flag=1;
            if((j&(j>>1)))  continue;//判断当前行是否有相邻的情况 
            if((mp[i]|j)!=mp[i]) continue;//判断是否在0的位置种草了
            for(int l=0;l<(1<<n);l++){
                if((l&(l>>1)))  continue;//判断上一行是否有相邻的情况 
                if((mp[i-1]|l)!=mp[i-1]) continue;
                if(l&j) continue;   //判断此行和上一行是否相邻 
                dp[i][j]+=dp[i-1][l];
                dp[i][j]%=mod;  
            }
        }
    }
    for(int i=0;i<(1<<n);i++){
        sum+=dp[m][i];
        sum%=mod;
    }
    cout<<sum;
}