【USACO2007 nov glod】玉米田

题面

农民 John 购买了一处肥沃的矩形牧场，分成M*N(1 <= M <= 12; 1 <= N <= 12)个 格子。他想在那里的一些格子中种植美味的玉米。遗憾的是，有些格子区域的土地是贫瘠的， 不能耕种。 精明的 FJ 知道奶牛们进食时不喜欢和别的牛相邻，所以一旦在一个格子中种植玉米，那么 他就不会在相邻的格子中种植，即没有两个被选中的格子拥有公共边。他还没有最终确定哪些 格子要选择种植玉米。

作为一个思想开明的人，农民 John 希望考虑所有可行的选择格子种植方案。由于太开明， 他还考虑一个格子都不选择的种植方案！请帮助农民 John 确定种植方案总数。

输入

• Line 1: 两个用空格分隔的整数 M 和 N

• Lines 2..M+1: 第 i+1 行描述牧场第i行每个格子的情况， N 个用空格分隔的整数，表示 这个格子是否可以种植(1 表示肥沃的、适合种植，0 表示贫瘠的、不可种植)

输出

• Line 1: 一个整数: FJ 可选择的方案总数 除以 100,000,000 的余数

分析

从数据范围+网格题很明显看出是个状压dp

状压dp的入门题。如果要选当前的格子，就不能选上下左右的，而我们一排一排来做，每次枚举本排的状态的时候，顺带检验一下与上一排的哪些状态不冲突。这就满足了与上下格子不冲突的条件。

而与左右格子不冲突需要每一行预处理出来。

当然还需要判断对于原地图的每一行来说，支不支持这样放。

定义dp[i][j]为做到第i行，第i行选j方案的总方案数。

最后的答案是∑dp[n][i](1≤i≤m)

代码

#include<bits/stdc++.h>
using namespace std;
#define N 19
#define M 65523
#define ll long long
#define mod 100000000
int dp[N][M];
int n,m,mx;
int e[N][N];
int mp[N];
bool ok[M];

int read(){
    int out = 0,flag = 1;char c = getchar();
    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
    return flag * out;
    }

int main()
{
    n=read();m=read();
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            e[i][j]=read();
            mp[i]=(mp[i]<<1)+e[i][j];//将地图转为二进制地图，比如如果一行3个都可以被开垦，则mp[i]==7（二进制为111）
        }
            
    mx=(1<<m)-1;//最大方案，即从一个格子都不选到每个格子都选的最大方案

    for(int i=0;i<=mx;i++)
        if( (((i<<1)&i)==0) )
            ok[i]=1;//预处理判断一行内是否冲突
            
    for(int i=0;i<=mx;i++)
        if((ok[i]) & ((i&mp[1])==i))
            dp[1][i]=1;//做dp之前需要先预处理出第一行
    
    for(int i=2;i<=n;i++)
        for(int j=0;j<=mx;j++)
            if((ok[j]) & ((j&mp[i])==j))
                for(int k=0;k<=mx;k++)
                    if((k&j)==0)
                        dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
    
    ll ans=0;
    for(int i=0;i<=mx;i++)
        ans=(ans+dp[n][i])%mod;
        
    cout<<ans;
    return 0;
}