UOJ Logo Zijian Online Judge

ZOJ

#38. 小猫咪和小老鼠

Statistics

题目背景

小猫咪和小老鼠是好朋友。

小猫咪不喜欢别人叫她小猫咪,因为她确实不是一只小猫咪,而是一只小老虎。一般猫咪更温顺可爱,而且不会在头上画一个王。

小猫咪有一个宝塔,能发光,能发出 $biubiubiu$ 的声音,还能被小猫咪弄丢!

小老鼠从某种意义上讲是小猫咪的下属,善于搜寻物品。

帮助小猫咪寻找丢失的宝塔已经成为日常了。显然小老鼠知道宝塔被丢在什么地方。不过今天日程比较紧,小老鼠决定路上把工作顺便完成了,防止过了 $deadline$ 被各种奇奇怪怪的领导查水表。

题目描述

以小老鼠所在位置为点 $(1,1)$ ,建立平面直角坐标系,已知宝塔在点 $(n,m)$ 。每个整点的位置上都有一个碎片,并有一定的开采难度。可以用 $A(i,j)$ 表示。

小老鼠希望规划一条从 $(1,1)$ 到 $(n,m)$ 的最短路径,她会沿途收集碎片。小老鼠能够开采当前位置的碎片,当且仅当这个位置的开采难度不低于她上一个开采位置的开采难度。

你只需要告诉她最多能开采到多少碎片。

输入格式

第一行包括两个整数 $n$ , $m$ 。

接下来 $n$ 行,每行 $m$ 个整数,用于描述每个整点所对应位置上的开采难度,其中第 $i+1$ 行的第 $j$ 个整数代表位置 $(i,j)$ 上的开采难度 $A(i,j)$ 。

输出格式

第一行包括一个整数,表示小老鼠最多能够开采到多少碎片。

样例一

input

5 5
1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
1 1 1 1 1 
1 1 1 1 1

output

7

样例二

见样例数据下载

限制与约定

对于$10\texttt{%}$的数据,$1 \leq n \leq 100$,$1 \leq m \leq 100$,

对于$40\texttt{%}$的数据,$1 \leq n \leq 500$,$1 \leq m \leq 200$,

对于$100\texttt{%}$的数据,$1 \leq n \leq 500$,$1 \leq m \leq 500$,$1 \leq A(i,j) \leq n \cdot m$,保证数据有梯度。

时间限制:$2\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载