TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7572
  • 题目
  • P7572[CSP-J 2020] 方格取数
    限制 : 时间限制 : 20000 MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

    设有 \(n \times m\) 的方格图,每个方格中都有一个整数。现有一只小熊,想从图的左上角走到右下角,每一步只能向上、向下或向右走一格,并且不能重复经过已经走过的方格,也不能走出边界。小熊会取走所有经过的方格中的整数,求它能取到的整数之和的最大值。

    输入格式

    \(1\) 行两个正整数 \(n,m\)
    接下来 \(n\) 行每行 \(m\) 个整数,依次代表每个方格中的整数。

    输出格式

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

    样例输入 1

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

    样例输出 1

    9

    样例输入 2

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

    样例输出 2

    -10

    提示

    样例1解释


    按上述走法,取到的数之和为 \(1+2+(-1)+4+3+2+(-1)+(-1)=9\) ,可以证明为最大值。


    注意,上述走法是错误的,因为第 \(2\) 行第 \(2\) 列的方格走过了两次,而根据题意,不能重复经过已经走过的方格。


    另外,上述走法也是错误的,因为没有走到右下角的终点。

    样例2解释


    按上述走法,取到的数之和为 \((-1)+(-1)+(-3)+(-2)+(-1)+(-2)=-10\) ,可以证明为最大值。因此,请注意,取到的数之和的最大值也可能是负数。

    数据范围

    对于 \(20\%\) 的数据, \(n,m\leq 5\)
    对于 \(40\%\) 的数据, \(n,m\leq 50\)
    对于 \(70\%\) 的数据, \(n,m\leq 300\)
    对于 \(100\%\) 的数据, \(1\leq n,m\leq 1000\)
    方格中整数的绝对值不超过 \(10^4\)