5159 收割机

题目描述

有一块土地，被划分成 $n\times m$ 的网格图（如图1），在这块土地上以网格为单位种植了不同的农作物，每个网格里有一个整数 $k$，表示当前网格的总产量。现在有一台智能收割机，它可以对任何农作物进行收割，收割机从网格图的左下角开始收割，只能往上或往右走，最终到达右上角位置，请问最多可以收割多少农作物。

网格图示例：

图1（n=3，m=4）

输入格式

第一行输入两个整数 $n$ 和 $m$，表示网格图大小。

第二行到第 $n+1$ 行，每行 $m$ 个整数 $k$ 用空格隔开。

输出格式

一个整数，表示收割农作物的产量。

样例输入 1

3 4
1 2 1 1
3 3 2 2
2 1 6 1

样例输出 1

14

数据范围与提示

$1\le n,m\le 30$，$0\le k\le 100$。

知识点与难度

• 知识点标签：动态规划基础、第十九讲(Level3)
• 原始难度：Mid-
• GESP 等级：6级（DP基础，基准分 1350）
• 题包分值：1550 分（基准 1350 + Mid- 难度浮动 +200）
• 时间限制：1000MS；空间限制：128MB

测试点分布