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

2024-03-24 08:31:58

1593：【例 2】牧场的安排

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

【题目描述】

原题来自：USACO 2006 Nov. Gold

Farmer John 新买了一块长方形的牧场，这块牧场被划分成 M 行 N 列 (1≤M≤12;1≤N≤12)，每一格都是一块正方形的土地。FJ 打算在牧场上的某几格土地里种上美味的草，供他的奶牛们享用。遗憾的是，有些土地相当的贫瘠，不能用来放牧。并且，奶牛们喜欢独占一块草地，于是 FJ 不会选择两块相邻的土地，即：没有哪两块草地有公共边。当然，FJ 还没有决定在哪些土地上种草。

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

【输入】

第 1 行：两个正整数 M 和 N，用空格隔开；

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

【输出】

第 1 行：输出一个整数，即牧场分配总方案数除以 10⁸ 的余数。

【输入样例】

2 3  
1 1 1  
0 1 0

【输出样例】

【提示】

样例说明

按下图把各块土地编号：

1 2 3  
0 4 0

只开辟一块草地有 4 种方案：选 1,2,3,4 中的任一块。开辟两块草地的话，有 3 种方案：13,14 以及 34。选三块草地只有一种方案：134。再加把牧场荒废的那一种，总方案数为 4+3+1+1=9 种。

数据范围与提示：

1≤N,M≤12。

sol：这是一道状压dp（废话），由于我借鉴了自己国王的思路，光荣的变成最差解（时间和空间都是最劣的），dp[i][j][k]表示到第i行，放了j个牧草，这行的状态为k，暴力预处理+超暴力转移

#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('\n');
    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\n",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

码农公寓