| 题目名称 | 1251. 过河 |
|---|---|
| 输入输出 | rivera.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 8 |
| 题目来源 |
 cqw
于2012-11-06加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：25， 提交：73， 通过率：34.25% | ||||
 TBK |
100 | 0.015 s | 5.11 MiB | C++ |
 CAX_CPG |
100 | 0.027 s | 1.27 MiB | Pascal |
 Makazeu |
100 | 0.032 s | 1.97 MiB | C++ |
 ACdog |
100 | 0.032 s | 82.08 MiB | C |
 稠翼 |
100 | 0.034 s | 1.00 MiB | Pascal |
 chenge |
100 | 0.038 s | 1.15 MiB | Pascal |
 Truth.Cirno |
100 | 0.039 s | 5.72 MiB | C++ |
 HouJikan |
100 | 0.049 s | 3.21 MiB | C++ |
 QhelDIV |
100 | 0.049 s | 7.11 MiB | C++ |
 warrior |
100 | 0.051 s | 0.17 MiB | Pascal |
| 本题关联比赛 | |||
| 20121106 | |||
| 关于 过河 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
动态规划，关键是判断什么情况下跳不到
| ||||
|
BFS
used[1010][2530] --> used[位置][时间mod【c的最小公倍数】] 其中c[i]=a[i]+b[i] c最小公倍数<=2520 状态最多1000x2520种，最差O(300万) 搜索到答案直接输出 | ||||
|
@warrior 超级农夫
  王者自由
2012-11-06 15:49
5楼
| ||||
|
农夫竟然可以隔着木桩跳！！！！
你以为是超级玛丽啊！！！ 题能不能说清楚点啊…… warrior
2012-11-06 15:37
4楼
| ||||
|
模拟路过。。
 苏轼
2012-11-06 15:03
3楼
| ||||
|
…………暴力枚举的坑爹dp居然能过。。。。。。= =可以估算t>20000的时候如果不能到，，，基本上就是永远到不了的，，，（求大神数学证明！！= =…………
| ||||
|
HAOI2012 音量调节 同じ問題です。
Makazeu
2012-11-06 12:10
1楼
| ||||
cstdio
Abel·S【题目描述】
农夫每天去种地都要过一条河，这条河很宽，过河要走上面的木桩。木桩有n支，排成一排，从左岸延伸到右岸，编号从1到n。左岸在1号桩的左边，右岸在n号桩的右边。但这些木桩会定时升降，因此每天他都花不少时间在过河上。所以他想找一种最快过河的方法。
在时刻0，农夫在左岸，他要在最短时间内到达右岸。在任何时刻，每一支桩都只能处于升或降的其中一种状态。升起的桩才可以站上去，农夫只能站在升起的桩上或岸上。
每一支桩在时刻0都是降的状态，接着升起A分钟，降下B分钟，再升起A分钟后，再降下B分钟后，这样一直交替升降下去。例如：A=2，B=3的桩，在时刻0降，在时刻1，2升，在时刻3，4，5降，等等。A和B是常数时间，而且对于每一支桩都可能不同。
设在时刻t农夫站在p桩，那么在时刻t+1，农夫能走到p桩的左右5个桩上或岸上，也可以原地不动，当然桩是可站立的。例如，在5号桩，他能走到1，2，3，4，5，6，7，8，9，10号桩，或到左岸。
请帮农夫找一种能最快到达右岸的方法。
【输入格式】
第一行是桩的数目，n(5<n≤1000)。接下来的n行每一行有两个整数A和B(1≤A，B≤5)，用一个空格隔开。按从1到n的顺序描述每一支桩的升和降的间隔时间。
【输出格式】
只有一行，即最早到达右岸的时刻。当不可能到达右岸时，输出“NO”。
【样例输入】
10 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1
【样例输出】
4