#A0645. 顺手牵羊
顺手牵羊
题目背景
微隙在所必乘,微利在所必得。少阴,少阳。
题目描述
33DAI 进入了一个 行 列的二维数组。数组中每个位置都有一只羊,第 行第 列的羊的重量是 。
33DAI 一开始在 的位置,每次可以往右一步或者往下一步。即可以从 走到 或者 。但是不能走出这个数组,即不能走到下标小于 或大于 的位置。他走到 就会停下。
他每次到达一个位置就会牵走那里的羊,显然最终他一共走了 步,牵走了 头羊。33DAI 会在这些羊中拿出最重的 只羊送给 Kitten 作为她 10 月 9 日的生日礼物。他希望这些羊都足够重,他想知道所有牵羊方案中,哪种方案的最重的 只羊中最轻的那只羊最重。
说人话就是,从 走到 ,每次只能向右或者向下,求路径上的数中的第 名最大是多少。
输入格式
两个数 。
接下来 行,每行 个数,第 行第 列为 。
输出格式
输出第 大的数最大是多少。
3 3
1 6 5
8 4 7
9 2 1
5
可以走 1->6->5->7->1
这条路,这样第 重的羊的重量是 ,其他方案都不如这个方案。
5 5
52 92 99 100 89
13 98 47 44 13
11 93 40 39 81
32 66 22 52 28
21 18 29 85 52
81
5 7
65 47 52 52 17
84 46 59 45 8
40 100 39 89 84
51 21 55 38 5
8 34 26 24 11
45
数据规模与约定
对于 的数据,,,。
- 子任务 1(10 分):保证所有 都相等。
- 子任务 2(20 分):保证 。
- 子任务 3(30 分):保证 。
- 子任务 4(40 分):没有特殊限制。