首页 > 其他 > 详细

【p1879】[USACO06NOV]玉米田Corn Fields

时间:2018-10-12 23:20:37      阅读:43      评论:0      收藏:0      [点我收藏+]

标签:bool   turn   代码   pac   input   不能   using   reg   include   

Description

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

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

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

Input

第一行:两个整数M和N,用空格隔开。

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

Output

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

下面的\(n,m\)\(n\)\(m\)列,与题目描述不符.

难得做起了状压DP的题

表示有点懵.但是莫名其妙地A了 emmm

\(f[i]\)代表第\(i\)行的状态.就是输入的状态,这个东西的话就直接算就好了.
\[ (f[i]<<=1)|=x \]
初始化:\(dp[0][0]=1\)

那么我们需要枚举每一行,再枚举状态\(j\)判断当前行的状态\(f[i]\)是否会包含状态\(j\),即合法与否.

判断不能有相临的话,直接写一个函数即可
\[ return ((state& (state>>1))==0 \ and\ (state&(state<<1))==0); \]
这里就不多解释了.

然后再枚举上一行状态\(k\)是否与当前状态\(j\)不相邻.即上下\(&\)起来为0。

(这就涉及到了\(&\)的性质,两边为\(True\)才为\(True\))
\[ ans=\sum_{i=0}^{(1<<m)-1}f[n][i] \]
时间复杂度\(O(n \times 2^{m+1})\)

代码

#include<cstdio>
#include<cctype>
#define mod 100000000
#define R register
using namespace std;
inline void in(int &x)
{
    int f=1;x=0;char s=getchar();
    while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
    while(isdigit(s)){x=x*10+s-'0';s=getchar();}
    x*=f;
}
int res[15][15],f[18],n,m,dp[18][1<<15],ans;
inline bool ok(int state)
{
    return ((state&(state>>1))==0 and (state&(state<<1))==0);
}
int main()
{
    in(n),in(m);
    for(R int i=1;i<=n;i++)
        for(R int j=1,x;j<=m;j++)
        {
            in(x);
            (f[i]<<=1)|=x;
        }
    int state=(1<<m)-1;
    dp[0][0]=1;
    for(R int i=1;i<=n;i++)
        for(R int j=0;j<=state;j++)
            if(ok(j) and (f[i]&j)==j)
                for(R int k=0;k<=state;k++)
                    if((k&j)==0)
                        (dp[i][j]+=dp[i-1][k])%=mod;
    for(R int i=0;i<=state;i++)
        (ans+=dp[n][i])%=mod;
    printf("%d",ans%mod);
}

【p1879】[USACO06NOV]玉米田Corn Fields

标签:bool   turn   代码   pac   input   不能   using   reg   include   

原文:https://www.cnblogs.com/-guz/p/9780622.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号