poj3254-二进制状态压缩

第一次接触二进制状态压缩 感觉很玄学很厉害
这里是原题
这里是我当时看的题解
题目大意：有n*m（1<=n,m<=12）的矩形草场 能放牛地方用1表示 不能的地方用0表示 两头牛不能挨着 求有多少种放牛方法（放0头牛也算一种方法）
嗷我翻译的好垃圾

很明显是一道dp题 dp[i][j] i为第几行 j为草场状态（如：100011101）
可以将草场状态看作二进制 然后用int 表示

主要就是经典的n3算法 其他细节我在代码里注明

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n,m,map[20],st[5000],tmp;//map储存给出的图 st储存满足“不相邻”条件的状态（预处理） tmp是个人习惯 一个临时变量
long long dp[20][5000],ans;
bool pd(int i,int j){
return (map[i]&st[j]);
}//这个在后面会解释
int main(){

while( scanf("%d%d",&n,&m)==2 ){
memset(dp,0,sizeof dp);
memset(map,0,sizeof map);

for(int i=1;i<=n;++i){
for(int j=0;j<m;++j){
scanf("%d",&tmp);
if(!tmp)
map[i]+=( 1<<j );
            }

        }
/*
 ↑把给出的草场状态反过来储存 用1储存不能放牛的 用0储存能放牛的 
 这样就能直接进行&运算判断状态是否合法
 （ 如果&！=0 说明在不能放牛（1）的地方放了牛（1） ）
 */
int r=1<<m;//最大值

int k=0;  
for(int i=0;i<r;i++){  
if(i&(i<<1))continue;//若i&i左移一位==0 说明没有两头相邻的牛

            st[k++]=i;  //用st储存所有满足 “不相邻”的状态 算是个小优化
        }  
        k--;//个人习惯
for(int j=0;j<=k;++j){
if(!pd(1,j))dp[1][j]=1;
//pd（i，j==0） 情况 st[j] 满足 第i行 （所有不能放牛（1）的地方都没有放牛（不为1））
        }


for(int i=2;i<=n;++i){
for(int j=0;j<=k;++j){

if(pd(i,j))continue;  //当前状态st[j]是否可在第i行存在 如不能 continue
for(int f=0;f<=k;++f){
if(((st[f]&st[j])==0)&& pd(i-1,f)==0 )//状态st[f]既要 [能在第i-1行存在]又要 [与当前状态st[j]不矛盾（上下没有两头牛相邻 即没有两个对位的1）]
                    dp[i][j]+=dp[i-1][f];
                }   
            }

        }
        ans=0;
for(int j=0;j<=k;++j){
            ans+=dp[n][j];
            ans%=100000000;
        }
printf("%lld\n",ans);
    }

return 0;
}

个人认为是很有意义的一道题