T30220:星际贸易航线

dp, http://cs101.openjudge.cn/practice/30220/

你是一艘星际货船的船长，正执行一项从银河系边缘前往核心星区的长途运输任务。

星图被表示为一个 N 行 M 列的网格。你的旅程从左上角 (1, 1) 开始，终点是右下角 (N, M)。为了利用引力弹弓效应节省燃料，你在每一步只能向右或向下移动。

网格中的每个区域都有一个数值，代表经过该区域时的航行结果：

正数：表示安全的贸易区，你可通过货物交易获得收益。
负数：表示危险区域（例如小行星带或海盗出没区），会导致船体损伤或燃料泄漏，从而造成损失（即资金扣除）。

你的飞船配备了一套实验性的“暗物质偏转护盾”。在整个航程中，你可以选择在恰好一个危险区域（负值格子）上激活该护盾。护盾不仅能完全吸收伤害，还能将冲击能量转化为辅助推进力，使原本的损失转变为等量的收益（即数值 x 变为 -x；例如，-100 的损失会变成 +100 的收益）。注意：如果你规划的路径全部由正数组成，则你不能也不需要使用护盾。

请规划一条航线，并策略性地使用护盾，使得抵达目的地时获得的总净收益最大。

输入

第一行包含两个整数 N 和 M，1 ≤ N, M ≤ 500。

接下来的 N 行，每行包含 M 个整数，表示网格中每个区域的收益或损失值。网格中的数值范围为 [−100, 100]。

输出

输出一个整数，表示所能获得的最大总净收益。

样例输入

sample1 input:
2 3
1 -5 3
-2 4 -1

sample1 output:
9

样例输出

sample2 input:
5 5
34 -64 -66 35 -84
42 67 -61 -76 -11
-91 -99 -89 -50 -15
-87 -84 -75 -95 52
-33 -7 -79 -36 -96

sample2 output:
128

提示

tags: search, dp

来源

2025fall TA-lxy

这个问题是一个典型的动态规划（DP）问题。虽然背景和“Turtle Strikes Back”类似，但目标变成了最大化自己的收益，并且你可以主动选择翻转哪一个负值格子。

解题思路

定义状态：由于我们只能使用恰好一次（或零次，如果路径全正）护盾，我们需要在 DP 状态中记录是否已经使用了护盾。
- dp0[i][j]：到达格子 $(i, j)$ 且未使用护盾时的最大收益。
- dp1[i][j]：到达格子 $(i, j)$ 且已经使用过一次护盾时的最大收益。
状态转移：对于每个格子 $(i, j)$ ，其值设为 $v$ ：
- 更新 dp0[i][j]：只能从左边或上边的 dp0 转移而来： $d p 0 [i] [j] = max (d p 0 [i - 1] [j], d p 0 [i] [j - 1]) + v$
- 更新 dp1[i][j]：有两种情况可以达到“已使用护盾”的状态：
  1. 护盾在之前的路径上已经用过了：从左边或上边的 dp1 转移，加上当前值 $v$ 。 $r e s_c a r r y = max (d p 1 [i - 1] [j], d p 1 [i] [j - 1]) + v$
  2. 护盾正好在当前格子使用：前提是当前值 $v < 0$ 。此时从左边或上边的 dp0 转移，加上翻转后的值 $- v$ 。 $r e s_u s e_n o w = max (d p 0 [i - 1] [j], d p 0 [i] [j - 1]) - v$
  取两者中的最大值： $d p 1 [i] [j] = max (r e s_c a r r y, r e s_u s e_n o w)$
特殊情况：
- 起点 $(0, 0)$ ：如果 $v < 0$ ，可以立即使用护盾， $d p 1 [0] [0] = - v$ ；否则 $d p 1$ 为负无穷。
- 全正路径：如果整条路径没有负数，则 dp1 会保持为极小的负数，最终结果取 max(dp0[N-1][M-1], dp1[N-1][M-1]) 即可。

Python 代码实现

python

import sys

def solve():
    # 使用 fast I/O 读取所有输入
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    it = iter(input_data)
    
    try:
        N = int(next(it))
        M = int(next(it))
    except StopIteration:
        return
    
    # 极大负数初始化
    inf = 10**15
    # dp0[j] 表示当前行第 j 列未使用护盾的最大值
    # dp1[j] 表示当前行第 j 列已使用一次护盾的最大值
    dp0 = [-inf] * M
    dp1 = [-inf] * M
    
    for i in range(N):
        # cur0_prev 和 cur1_prev 记录当前行左侧格子的状态 (用于横向转移)
        cur0_prev = -inf
        cur1_prev = -inf
        
        for j in range(M):
            val = int(next(it))
            
            # --- 1. 计算 dp0 (不使用护盾) ---
            if i == 0 and j == 0:
                cur0 = val
            else:
                # 只能从上方 (dp0[j]) 或左方 (cur0_prev) 转移
                up0 = dp0[j]
                prev0 = up0 if up0 > cur0_prev else cur0_prev
                cur0 = prev0 + val
            
            # --- 2. 计算 dp1 (使用一次护盾) ---
            # 方案 A: 护盾在之前已经用过了
            up1 = dp1[j]
            prev1 = up1 if up1 > cur1_prev else cur1_prev
            res_carry = prev1 + val
            
            # 方案 B: 在当前格子使用护盾 (仅当 val < 0)
            res_use_now = -inf
            if val < 0:
                if i == 0 and j == 0:
                    res_use_now = -val
                else:
                    # prev0 是到达当前格子的不使用护盾的最大前驱路径
                    res_use_now = prev0 - val
            
            # 取两种方案的最优值
            cur1 = res_carry if res_carry > res_use_now else res_use_now
            
            # 更新状态数组，供下一列/下一行使用
            dp0[j] = cur0
            dp1[j] = cur1
            cur0_prev = cur0
            cur1_prev = cur1
            
    # 最终结果是到达终点时，用过护盾或没用过护盾的最大收益
    ans = dp0[M-1] if dp0[M-1] > dp1[M-1] else dp1[M-1]
    sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    solve()

算法复杂度

时间复杂度： $O (N \times M)$ 。我们只对网格进行了一次线性扫描。
空间复杂度： $O (M)$ 。由于当前状态只取决于上一行和左侧格子的状态，我们使用了滚动数组（1D 数组）来优化空间。

与 2194E 题目的区别

2194E：博弈性质。Raphael 先翻转一个点来最小化结果，Michelangelo 后手最大化路径。需要考虑整条对角线的性质。
本题：纯最优化问题。你同时控制路径选择和翻转选择，目标是最大化。这可以用简单的扩展状态 DP 解决。

2194E. The Turtle Strikes Back, dp, https://codeforces.com/problemset/problem/2194/E

T30220:星际贸易航线 ​

T30220:星际贸易航线