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

circlegg · 2017-05-05 11:54:43 · 题解

比较简洁的解

···

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,t,map[15],d[15][(1<<13)+5],way[1<<13],w,ans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&t);
            t=t==0?1:0;//反过来存图方便后面位运算
            map[i]|=t<<(j-1);
        }
    }
    for(int i=0;i<=(1<<m)-1;i++){
        if((i&(i<<1))==0){
            way[++w]=i;//将所有可能的行的情况处理，加快枚举
        }
    }
    for(int i=1;i<=w;i++){
        if((way[i]&map[1])==0){
            d[1][way[i]]=1;//dp数组赋初值
        }
    }
    for(int k=2;k<=n;k++){
        for(int i=1;i<=w;i++){
            for(int j=1;j<=w;j++){
                if(((way[i]&map[k])==0)&&((way[i]&way[j])==0)){
                    d[k][way[i]]+=d[k-1][way[j]];//转移
                    d[k][way[i]]%=1000000000;    
                }
            }
        }
    }
    for(int i=1;i<=w;i++){
        ans+=d[n][way[i]];//最后一行所有情况求和
        ans%=1000000000;
    }
    printf("%d",ans);
    return 0;
}

···