题目名称 757. [USACO Nov06] 牧场的安排
输入输出 cowfood.in/out
难度等级 ★★
时间限制 1000 ms (1 s)
内存限制 128 MB
测试数据 10 简单对比
题目来源 2012-04-14
开放分组 全部用户
提交状态
分类标签
USACO 动态规划 状态压缩
通过:72, 提交:173, 通过率:41.62%
GravatarHZOI_蒟蒻一只 100 0.000 s C++
Gravatar瑆の時間~無盡輪迴·林蔭 100 0.000 s C++
Gravatarlqwang1985 100 0.001 s Pascal
Gravatartaxuig 100 0.002 s C++
GravatarHallmeow 100 0.002 s C++
Gravataryymxw 100 0.002 s C++
Gravatarassassain 100 0.002 s C++
GravatarBaDBoY 100 0.002 s C++
Gravatar转瞬の电流 100 0.002 s Pascal
Gravatar0_0 100 0.002 s C++
关于 牧场的安排 的讨论
狀態壓縮動態規劃
Status-Compressed Dynamic Programming。EASY。
GravatarMakazeu
2012-04-16 16:56 1楼
我的代码有注释哦~
Gravatar0
2015-07-30 16:42 2楼
Gravatar一個人的雨
2015-08-02 17:04 3楼
Gravatar转瞬の电流
2017-03-28 21:08 4楼
我是真的不适合DP= =
打个这个卡死我= =
GravatarHzoi_Mafia
2017-05-31 08:19 5楼
忘了%mod
GravatarBaDBoY
2017-05-31 09:12 6楼
卡常技巧:用变量定义常用计算 get√
预先手算最大值 get√
GravatarHZOI_蒟蒻一只
2017-06-09 20:54 7楼
index会编译错误。再也不相信别人的题解了
GravatarAlfal
2019-07-10 14:48 8楼

757. [USACO Nov06] 牧场的安排

★★   输入文件:cowfood.in   输出文件:cowfood.out   简单对比
时间限制:1 s   内存限制:128 MB

Description  [USACO Nov2006 Gold]

Farmer John新买了一块长方形的牧场,这块牧场被划分成M列N行(1<=M<=12; 1<=N<=12),每一格都是一块正方形的土地。

FJ打算在牧场上的某几格土地里种上美味的草,供他的奶牛们享用。遗憾的是,有些土地相当的贫瘠,不能用来放牧。

并且,奶牛们喜欢独占一块草地的感觉,于是FJ不会选择两块相邻的土地,也就是说,没有哪两块草地有公共边。

当然,FJ还没有决定在哪些土地上种草。 作为一个好奇的农场主,FJ想知道,如果不考虑草地的总块数,那么,一共有多少种种植方案可供他选择。

当然,把新的牧场荒废,不在任何土地上种草,也算一种方案。请你帮FJ算一下这个总方案数。

Input

* 第1行: 两个正整数M和N,用空格隔开 * 第2..M+1行: 每行包含N个用空格隔开的整数,描述了每块土地的状态。

输入的第i+1行描述了第i行的土地。所有整数均为0或1,是1的话,表示这块土地足够肥沃,0则表示这块地上不适合种草

Output

* 第1行: 输出一个整数,即牧场分配总方案数除以100,000,000的余数

Sample Input

2 3
1 1 1
0 1 0


Sample Output

9

输出说明:

按下图把各块土地编号:

1 2 3
4

只开辟一块草地的话,有4种方案:选1、2、3、4中的任一块。

开辟两块草地的话,有3种方案:13、14以及34。选三块草地只有一种方案:134。

再加把牧场荒废的那一种,总方案数为4+3+1+1=9种。