#3712. 神秘的数字迷宫

神秘的数字迷宫

题目描述

神秘的数字迷宫

在遥远的数字王国中,存在着一个充满神秘与挑战的数字迷宫。迷宫由 n 行 m 列的方格组成,每行方格上各有一个整数,这些整数可能相同,也可能不同。迷宫的入口位于左上角的方格(第 1 行第 1 列),出口位于右下角的方格(第 n 行第 m 列)。

小明计划探索这个迷宫。他从入口开始,每步可以向下走或向右走,直到出口。但是,当小明的脚上沾有数字 x 时,地面的数字 y 将会以奇妙的方式改变,变成 (y - x) 的值。然而,这种魔法效果只会持续一小步时间。更神奇的是,当小明的脚下出现了数字 z,而他的脚下 previously 是数字 w 时,数字 z 将会显示为 (z + w) 的值。

假设小明的初始脚步上没有附着任何数字,请求出他能离开出口的最大学生气值。即是说,请求出所有可能的路径中,所有经过的数字(经过时都进行了相应的变化)的和的最大值。请帮助小明,告诉他如何穿过这个迷宫,获得最大的学生气值!

输入格式

推荐使用与 [题目] 相同的读取方式。

输出格式

输出单一行,包含一个整数,为答案。

提示

数据范围

Time limit per test: 2.0 seconds Memory limit per test: 256.0 megabytes

输入输出示例 1

3 3
1 2 3
4 5 6
7 8 9
39

样例 1 解释

  • 对应的最大学生气值路径为:1 → 5 → 9 → 8 → 6。
  • 按照规则,小明的每一步都从脚下数字获得气值,并把气值累加到最终结果中。具体步骤如下: * 在起始点,小明获得了 1 的气值。 * 接着,他向右走,在数字 2 上获得了 2 − 1 = 1 的气值。 * 接着,他向下走,在数字 5 上获得了 5 − 2 = 3 的气值。 * 接着,他向下走,在数字 8 上获得了 8 − 5 = 3 的气值。 * 接着,他向右走,在数字 6 上获得了 6 − 8 = -2 的气值。

累加和为:1 + 1 + 3 + 3 + (-2) = 6。 * 事实上,本示例中存在其他获得同样大值的路径,这里列出的一种路径的气值累加和为 39。* (默认折行的输出被强制禁用,所有示例的输出将以原始格式显示。)

输入输出示例 2

3 5
1 3 5 7 9
1 2 3 4 5
1 7 15 15 18
39

输入格式

输入占一行为两个正整数 n, m (1 ≤ n, m ≤ 1000)。 接下来的 n 行,每行含 m 个正整数 aij (1 ≤ aij ≤ 10^5)。

格式说明

本题目的输入读取方式与 [题目] 完全相同。

注意

输入数据即使用于 [标题]。在任何情况下,你不得为 [标题] 提供任何额外的数据读取方法。

选项

为避免多行输入中的意外换行,输入的所有数字都写在一行内,用空格分隔。

为了在 Web 端方便提交,本题目的输入格式与 [题目] 完全相同。

输出格式

输出本题目的正确答案,占一行。

格式说明

输出本题目的答案时,请参照 [示例] 中的输出格式。

注意

请确保在任何情况下都只输出本题目的答案。不要输出附加的信息。

为了在 Web 端方便提交,本题目的输出格式与 [题目] 完全相同。

样例

3 3
1 2 3
4 5 6
7 8 9
20 
3 5
1 3 5 7 9
1 2 3 4 5
1 7 15 15 18
47 

说明/提示

提示

  • 线段树的妙用
  • 动态规划的优化

解析

神秘的数字迷宫

解题思路

这个问题是一个动态规划问题。我们需要找到一条从网格的左上角到右下角的路径,使得路径上所有经过的数字(经过时进行相应的变化)的和最大。

根据题意,每步移动时,当前方格的值会根据上一步的值进行变化。具体来说,当step从 (i,j) 移动到 (i,j+1) 时,新的值是 (y - x),其中 x 是上一步的值,y 是当前方格的值。但是,这种变化是瞬时的,不影响其他步骤。

然而,当从 (i,j) 移动到 (i+1,j) 时,显示的值是 (z + w),其中 z 是当前方格的值,w 是上一步的值。

这似乎是一个标准的路径问题,但状态的定义却有些复杂。我们可以通过分析每步的转移来定义合适的状态。

动态规划定义

设 dp[i][j] 为到达 (i,j) 时的最大气值和。由于每步的气值取决于上一步的值和当前的值,因此我们需要在 dp 中记录到达 (i,j) 时的当前值,以便在下一步计算时使用。

然而,直接使用 dp[i][j] 表示到达 (i,j) 时的当前值是不够的,因为下一步的气值计算需要上一步的值。因此,我们需要在 dp 状态中包含上一步的值,或者找到其他方式来表示这种依赖关系。

算法选择理由

根据上述分析,每步的气值计算都与上一步的值有关。因此,传统的动态规划方法可能不适用,因为状态需要携带上一步的值。但是,这在 n 和 m 达到 1000 的情况下是不现实的,因为它会使得状态空间变得极其庞大。

但仔细观察可以发现,当从 (i,j-1) 向右移动到 (i,j) 时,当前方格的值 y 会被计算为 y - prev (prev 是上一步的值)。而当从 (i-1,j) 向下移动到 (i,j) 时,当前方格的值 z 会被显示为 z + prev。因此,每步的气值计算方式不同。

这提示我们,到达 (i,j) 的最大气值和不仅与 (i,j) 的值有关,还与进入 (i,j) 时的 prev 值有关。因此,我们需要在动态规划的状态中包含 prev 值,或者找到其他方式来表示这种关系。

然而,这似乎是一个无法解决的问题,因为 prev 值可以是任何可能的值,导致状态空间变得不可管理。但可能存在着某些规律或者优化,使得我们可以不显式地存储 prev 值。

复杂度分析

假设使用普通的动态规划,对于每个 (i,j) 都需要考虑从上方或左方过来,并且计算每种情况下的最大值。这样,时间复杂度是 O(nm)的,因为每个单元格只被访问一次。空间上,使用一个 n x m 的 dp 表,也是 O(nm)的。

对于 n 和 m 达到 1000,这种复杂度是 acceptable 的,因为 1e6 级别的操作在 2 秒内是可以处理的。

具体实现

在代码中,我们可以定义 dp[i][j] 为到达 (i,j) 时的最大气值和。对于每个单元格 (i,j) ,我们从上方 (i-1,j) 或左方 (i,j-1) 移动过来。每种情况下的气值计算方式不同。

当从上方下来时,当前方格的值是 a[i][j],上一步的值是 dp[i-1][j]。根据规则,显示的值是 (a[i][j] - prev),这里 prev 是上一步的值。所以,dp[i][j] = max(dp[i][j], dp[i-1][j] + (a[i][j] - dp[i-1][j]))。

当从左方过来时,显示的值是 (a[i][j] + prev)。所以,dp[i][j] = max(dp[i][j], dp[i][j-1] + (a[i][j] + dp[i][j-1]))。

但这里有一个问题,当从对角线方向过来时,比如从 (i-1,j-1) 移动到 (i,j),这种情况下,如何计算气值呢?根据题意,每步只能向下或右移,所以不涉及对角线。因此,每步要么来自上方,要么来自左方。

所以,对于每个 (i,j) ,只需要考虑从 (i-1,j) 或 (i,j-1) 移动过来的情况。

样例解析

在样例 1 中,3x3 的网格。最优点的路径是先向右走,再向下,再向下,再右走。每步的气值变化都符合预期。

代码实现

代码使用了一个 n x m 的 dp 表。初始时,dp[0][0] = a[0][0]。然后,对于每个单元格 (i,j) ,从上方和左方取最大值更新 dp[i][j]。

通过这种方式,我们可以正确地计算出每步的最大气值和。

注意事项

由于数据规模较大(1000x1000),需要使用 64 位整数类型 (long long) 来存储 dp 值,以防止溢出。同时,初始状态时,dp[0][0] 已经是 a[0][0]。

在代码实现时,需要正确处理边界情况,比如当 i=0 时无法从上方转移,j=0 时无法从左方转移。因此,在计算每个单元格时,需要分别检查是否可以从上方或左方转移过来。

通过这些步骤,我们可以正确地解决问题,并在规定的时间内处理大输入。

来源

AI 生成 · olympiccoder:7b · 提高+/省选- · 线段树