2020 T4 方格取数

主知识点：动态规划。交叉标签：动态规划、深搜。
暴力标注：DP 可用暴力拿部分分。
OJ 使用标准输入与标准输出。原比赛文件名为 number.in / number.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 1 秒；内存 256 MiB；测试点 20；总分 100。
数据来源：公开存档数据；未逐文件对照官网下载包。

题目描述

一个 $n\times m$ 网格含整数。从左上角 $(1,1)$ 走到右下角 $(n,m)$，每步只能向上、向下或向右移动一格，不能越界，不能重复经过格子。求路径经过的所有格子数值之和的最大值，包含起点与终点。

输入格式

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

接下来 $n$ 行每行 $m$ 个整数，依次代表每个方格中的整数。

输出格式

一个整数，表示小熊能取到的整数之和的最大值。

样例

样例 1

输入：

3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1

输出：

9

样例 2

输入：

2 5
-1 -1 -3 -2 -7
-2 -1 -4 -1 -2

输出：

-10

数据范围与特殊性质

• 对于 $20\%$ 的数据，$n, m \le 5$。

• 对于 $40\%$ 的数据，$n, m \le 50$。

• 对于 $70\%$ 的数据，$n, m \le 300$。

• 对于 $100\%$ 的数据，$1 \le n,m \le 10^3$。方格中整数的绝对值不超过 $10^4$。

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

暴力退路标注（教学补充）

DP 可用暴力拿部分分。DFS 枚举上、下、右移动，访问数组禁止重复格子，到达终点更新最大和。n,m≤5 的前 20% 是目标，最坏仍需控制搜索量。不能把只能向右/向下的普通 DP 当本题正解。

目标范围：20 分小网格，需剪枝并留意耗时。部分分按原题规模判断，不构成对任意实现或评测机的得分保证。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P7074
• 赛事：CSP-J 第二轮入门级 2020。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。