| 题目名称 | 757. [USACO Nov06] 牧场的安排 |
|---|---|
| 输入输出 | cowfood.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-04-14加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：89， 提交：173， 通过率：51.45% | ||||
 HZOI_蒟蒻一只 |
100 | 0.000 s | 0.00 MiB | C++ |
 瑆の時間~無盡輪迴·林蔭 |
100 | 0.000 s | 0.00 MiB | C++ |
 lqwang1985 |
100 | 0.001 s | 0.21 MiB | Pascal |
 taxuig |
100 | 0.002 s | 0.32 MiB | C++ |
 Hallmeow |
100 | 0.002 s | 0.34 MiB | C++ |
 yymxw |
100 | 0.002 s | 0.34 MiB | C++ |
 assassain |
100 | 0.002 s | 0.56 MiB | C++ |
 BaDBoY |
100 | 0.002 s | 0.59 MiB | C++ |
 转瞬の电流 |
100 | 0.002 s | 0.60 MiB | Pascal |
 0_0 |
100 | 0.002 s | 0.75 MiB | C++ |
| 本题关联比赛 | |||
| 2024暑假C班集训A | |||
| 关于 牧场的安排 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
index会编译错误。再也不相信别人的题解了
 Deacep
2019-07-10 14:48
8楼
| ||||
|
卡常技巧：用变量定义常用计算 get√
预先手算最大值 get√ HZOI_蒟蒻一只
2017-06-09 20:54
7楼
| ||||
|
忘了%mod
 | ||||
|
我是真的不适合DP= =
打个这个卡死我= =   Hzoi_Mafia
2017-05-31 08:19
5楼
| ||||
|
| ||||
|
| ||||
|
我的代码有注释哦~
| ||||
|
狀態壓縮動態規劃
Status-Compressed Dynamic Programming。EASY。 | ||||
一個人的雨
0
MakazeuDescription [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
1 1 1
0 1 0
Sample Output
9
输出说明:
按下图把各肥沃地块土地编号：
1 2 3
0 4 0
只开辟一块草地的话，有4种方案：选1、2、3、4中的任一块。
开辟两块草地的话，有3种方案：13、14以及34。选三块草地只有一种方案：134。
再加把牧场荒废的那一种，总方案数为4+3+1+1=9种。