热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

[USACO2006NovemberGold]玉米地CornFields

题目描述FarmerJohn新买了一块长方形的牧场,这块牧场被划分成M行N列(1<M<12;1<N<12),每一格都是一块正方形的土地。FJ打

题目描述

  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行: 输出一个整数,即牧场分配总方案数除以100,000,000的余数


样例数据

样例输入

2 3
1 1 1
0 1 0

样例输出

9

样例解释

这里写图片描述


数据规模

1 ≤ N,M ≤ 12


题目分析

状压Dp裸题,和poj2411不太一样,每一行状态并不完全相同,因此还需判断枚举出来的状态是否是合法状态子集。


源代码
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
inline const int Get_Int() {
    int num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
        if(x=='-')bj=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9') {
        num=num*10+x-'0';
        x=getchar();
    }
    return num*bj;
}
int ans,f[15][2005],State[15],n,m,Max;
int main() {
    n=Get_Int();
    m=Get_Int();
    Max=(1<1;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            State[i]=(State[i]<<1)+Get_Int();
    for(int i=0; i<=Max; i++)
        if((i|State[1])==State[1]&&(i&(i<<1))==0)f[1][i]=1; //不超过指定状态且没有相邻的1的状态有效 
    for(int i=2; i<=n; i++)
        for(int j=0; j<=Max; j++) //枚举上一行状态j
            for(int k=0; k<=Max; k++) //枚举此行状态k
                if((k&j)==0&&(k|State[i])==State[i]&&(k&(k<<1))==0)f[i][k]=(f[i][k]+f[i-1][j])%100000000;
    for(int i=0; i<=Max; i++)ans=(ans+f[n][i])%100000000;
    printf("%d\n",ans);
    return 0;
}


推荐阅读
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • Codeforces Round #566 (Div. 2) A~F个人题解
    Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意:给你一个的表格,你 ... [详细]
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • 本题探讨了一种字符串变换方法,旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量,从而确定转换的可能性。 ... [详细]
  • 本文基于刘洪波老师的《英文词根词缀精讲》,深入探讨了多个重要词根词缀的起源及其相关词汇,帮助读者更好地理解和记忆英语单词。 ... [详细]
  • 使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表
    本文介绍了一段通用代码示例,该代码不仅能够操作 Azure Active Directory (AAD),还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级:AAD 和 Subscription。 ... [详细]
  • 前言--页数多了以后需要指定到某一页(只做了功能,样式没有细调)html ... [详细]
  • DNN Community 和 Professional 版本的主要差异
    本文详细解析了 DotNetNuke (DNN) 的两种主要版本:Community 和 Professional。通过对比两者的功能和附加组件,帮助用户选择最适合其需求的版本。 ... [详细]
  • 本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度,而 vector 是一种可扩展的容器,允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景,并提供了代码示例以加深理解。 ... [详细]
  • 本题涉及一棵由N个节点组成的树(共有N-1条边),初始时所有节点均为白色。题目要求处理两种操作:一是改变某个节点的颜色(从白变黑或从黑变白);二是查询从根节点到指定节点路径上的第一个黑色节点,若无则输出-1。 ... [详细]
  • 利用决策树预测NBA比赛胜负的Python数据挖掘实践
    本文通过使用2013-14赛季NBA赛程与结果数据集以及2013年NBA排名数据,结合《Python数据挖掘入门与实践》一书中的方法,展示如何应用决策树算法进行比赛胜负预测。我们将详细讲解数据预处理、特征工程及模型评估等关键步骤。 ... [详细]
  • C++: 实现基于类的四面体体积计算
    本文介绍如何使用C++编程语言,通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式,并提供了两种不同的实现方式。 ... [详细]
  • 本文详细介绍了C语言的起源、发展及其标准化过程,涵盖了从早期的BCPL和B语言到现代C语言的演变,并探讨了其在操作系统和跨平台编程中的重要地位。 ... [详细]
author-avatar
吃饭睡觉v
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有