洛谷P1879 [USACO06NOV]Corn Fields G 题解

题目链接：P1879 [USACO06NOV]Corn Fields G

题意：

农场主 \(\rm John\) 新买了一块长方形的新牧场，这块牧场被划分成 \(M\) 行 \(N\) 列 \((1 \le M \le 12; 1 \le N \le 12)\)，每一格都是一块正方形的土地。 \(\rm John\) 打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。

遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是 \(\rm John\) 不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。

\(\rm John\) 想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）

状压经典题

首先把每一行的情况压到状态 \(F_i\) 中

可以预处理所有状态（选择哪些种草）在行上是否合法

例如两块草不能相邻选，当然此时不用考虑可不可以种

判断依据如下

int mx=1<<n;
for(int i=0; i<mx; i++)
    st[i]=( ((i&(i<<1))==0) && ((i&(i>>1))==0) );

然后枚举状态转移

时间复杂度 \(O(n2^{2n})\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(15)
const int p=1e9;
bool st[5005];
int n,m,mp[N][N],F[N],f[N][5005];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> m >> n;
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
            cin >> mp[i][j];
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
            F[i]=(F[i]<<1)+mp[i][j];
    int mx=1<<n;
    for(int i=0; i<mx; i++)
        st[i]=( ((i&(i<<1))==0) && ((i&(i>>1))==0) );
    f[0][0]=1;
    for(int i=1; i<=m; i++)
        for(int j=0; j<mx; j++)
            if(st[j] && ((j&F[i])==j))
                for(int k=0; k<mx; k++)
                    if((k&j)==0) f[i][j]=(f[i][j]+f[i-1][k])%p;
    int res=0;
    for(int i=0; i<mx; i++)
        res+=f[m][i],res%=p;
    cout << res << '\n';
    return 0;
}