P1879 [USACO06NOV]玉米田Corn Fields

题目描述

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

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

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

输入输出格式

输入格式：

第一行：两个整数\(M\)和\(N\)，用空格隔开。

第2到第\(M+1\)行：每行包含\(N\)个用空格隔开的整数，描述了每块土地的状态。第i+1行描述了第i行的土地，所有整数均为\(0\)或\(1\)，是\(1\)的话，表示这块土地足够肥沃，0则表示这块土地不适合种草。

输出格式：

一个整数，即牧场分配总方案数除以\(100,000,000\)的余数。

---

做的第一道状压\(DP\)，总结一下。

\(dp[i][j]\)表示第\(i\)行状态\(j\)(用二进制代表每一位是否种植，例如01010，就是当前行2和4种田)

转移：\(dp[i][j]=\sum dp[i-1][k]\),其中\(k\)为上一行的合法状态。

复杂度：\(O(2^{2*m}*n*m)\)

其中，两个带2的次方的是当前行的枚举和上一行的枚举，\(n\)是行数，\(m\)是检测合法。

可能会爆，要剪一下枝。

发现每一行有很多状态其实都是不合法的，所以先\(dfs\)找到每一行对自己来说的合法状态。

code

#include <cstdio>

#include <cstring>

using namespace std;

const int N=13;

int dp[N][1<<N];

int g[N][N],n,m,cnt=0,t0[1<<N];

//第几行，第几个数字,状态，上一个数

void dfs(int line,int dep,int t,int last)

{

    if(dep==m+1)

    {

        t0[++cnt]=t;

        return;

    }

    if(g[line][dep]&&!last)

        dfs(line,dep+1,t<<1|1,1);

    dfs(line,dep+1,t<<1,0);

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

            scanf("%d",&g[i][j]);

    dfs(1,1,0,0);

    for(int i=1;i<=cnt;i++)

        dp[1][t0[i]]=1;

    for(int i=2;i<=n;i++)

    {

        cnt=0;

        dfs(i,1,0,0);

        for(int j=1;j<=cnt;j++)

            for(int k=0;k<=(1<<m)-1;k++)

            {

                if(!dp[i-1][k]) continue;

                int flag=1;

                for(int q=0;q<n;q++)

                    if((t0[j]>>q)&(k>>q))

                    {

                        flag=0;

                        break;

                    }

                if(flag)

                {

                    dp[i][t0[j]]+=dp[i-1][k];

                    dp[i][t0[j]]%=100000000;

                }

            }

    }

    int ans=0;

    for(int i=1;i<=cnt;i++)

    {

        ans+=dp[n][t0[i]];

        ans%=100000000;

    }

    printf("%d\n",ans);

    return 0;

}

---

2018.5.10