一本通1593【例 2】牧场的安排

1593：【例 2】牧场的安排

时间限制: 1000 ms 内存限制: 524288 KB

【题目描述】

原题来自：USACO 2006 Nov. Gold

Farmer John 新买了一块长方形的牧场，这块牧场被划分成 $M$

作为一个好奇的农场主，FJ 想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择。当然，把新的牧场荒废，不在任何土地上种草，也算一种方案。请你帮 FJ 算一下这个总方案数。

【输入】

第 $1$

第 $2$

【输出】

第 $1$

【输入样例】

2 3  
1 1 1  
0 1 0

【输出样例】

【提示】

样例说明

按下图把各块土地编号：

1 2 3  
0 4 0

只开辟一块草地有 $4$

数据范围与提示：

$1 \leq N, M \leq 12$

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-');
        ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48);
        ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x<10)
    {
        putchar(x+'0');
        return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
inline void writeln(ll x)
{
    write(x);
    putchar('
');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) writeln(x)
const int Mod=100000000;
int n,m,dp[15][12*12+5][(1<<12)+5];
int Zhuangt[15],Ges[(1<<12)+5];
bool Jud[(1<<12)+5],Can[(1<<12)+5][(1<<12)+5];
int main()
{
    int i,j,k,ii,jj;
    R(m); R(n);
    for(i=1;i<=m;i++)
    {
        int x;
        Zhuangt[i]=0;
        for(j=1;j<=n;j++)
        {
            R(x); if(x) Zhuangt[i]|=(1<<(j-1));
        }
    }
    for(i=0;i<(1<<n);i++)
    {
        bool bo=1;
        for(j=2;j<=n&&bo;j++) if((i&(1<<(j-2)))&&(i&(1<<(j-1)))) bo=0;
        Jud[i]=bo;
        Ges[i]=0;
        for(j=1;j<=n;j++) if(i&(1<<(j-1))) Ges[i]++;
    }
    for(i=0;i<(1<<n);i++) if(Jud[i])
    {
        for(j=0;j<(1<<n);j++) if(Jud[j])
        {
            bool bo=1;
            for(k=1;k<=n&&bo;k++) if(i&(1<<(k-1)))
            {
                if(j&(1<<(k-1))) bo=0;
            }
            if(bo)    Can[i][j]=1;
        }
    }
    for(i=0;i<(1<<n);i++) if(((i&Zhuangt[1])==i)&&(Jud[i])) dp[1][Ges[i]][i]=1;
    for(i=2;i<=m;i++)
    {
        for(j=0;j<=(i-1)*n;j++)
        {
            for(ii=0;ii<(1<<n);ii++) if(dp[i-1][j][ii])
            {
                for(jj=0;jj<(1<<n);jj++) if(Can[ii][jj]&&((jj&Zhuangt[i])==jj))
                {
                    dp[i][j+Ges[jj]][jj]+=dp[i-1][j][ii];
                    dp[i][j+Ges[jj]][jj]-=(dp[i][j+Ges[jj]][jj]>=Mod)?(Mod):0;
                }
            }
        }
    }
    int ans=0;
    for(i=0;i<=(n*m);i++)
    {
        for(j=0;j<(1<<n);j++) if(dp[m][i][j])
        {
//            printf("dp[%d][%d][%d]=%d
",m,i,j,dp[m][i][j]);
            ans+=dp[m][i][j];
            ans-=(ans>=Mod)?Mod:0;
        }
    }
    Wl(ans);
    return 0;
}
/*
input
2 3  
1 1 1  
0 1 0
output
9

input
1 10
1 1 1 1 1 1 1 1 1 1
output
144
*/

View Code