题解 | #收集金币#

1. 问题分析

本题是一个典型的带有动态约束的网格路径最优化问题。其核心特征在于：

移动限制：仅能向右或向下，构成了典型的有向无环图（DAG）结构。
时空约束：方格变为障碍点（墙）的时间 $v$ 是动态的。这意味着一个方格是否可行，不仅取决于其坐标 $(x, y)$ ，还取决于到达该方格的时间步。
即时判定：每一回合先发生变化，后进行移动。这意味着如果玩家计划在第 $k$ 回合进入方格 $(x, y)$ ，而该方格在第 $v \le k$ 回合变为墙，则该路径被切断。

关键点：到达时间计算 在 $n \times m$ 的网格中，从 $(1,1)$ 出发，到达任意位置 $(x, y)$ 所需的步数（即移动回合数）是固定的。由于每回合只能向下或向右移动一格，到达 $(x, y)$ 的总步数 $d$ 始终满足： $d = (x - 1) + (y - 1) = x + y - 2$ 因此，玩家在第 $d$ 回合动作结束后到达 $(x, y)$ 。

2. 算法：动态规划

鉴于路径的无后效性（只能向右向下），我们采用动态规划策略。

可通行性判定准由：根据题目描述，每一回合开始时方格先变化。玩家从 $(1,1)$ 到达 $(x, y)$ 的移动发生在第 $dist = x+y-2$ 个回合。

如果某个方格 $(x, y)$ 在第 $v$ 回合变为墙，且满足 $v \le x+y-2$ ，则当玩家尝试进入该方格时，它已经是墙。
特例处理：起点 $(1,1)$ 在第 1 回合变墙不影响玩家（题目明确说明）。实际上， $1+1-2=0$ ，由于 $v \ge 1$ ，公式 $v \le x+y-2$ 在 $(1,1)$ 处自然不成立，符合逻辑。

状态定义：设 $dp[i][j]$ 表示到达方格 $(i, j)$ 时能收集到的最大金币数。

状态转移方程：对于每个位置 $(i, j)$ ：

判定是否为墙：如果已知 $(i, j)$ 在第 $v$ 回合变墙，且 $v \le i+j-2$ （且 $(i, j) \neq (1, 1)$ ），则该点不可达，标记为 $dp[i][j] = -\infty$ 。
正常转移：若非墙，则： $dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) + a_{i,j}$ 注意：需处理边界情况，若上方和左方均不可达，则当前点亦不可达。

3. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    vector<vector<int>> wall(n + 1, vector<int>(m + 1, INF));
    int t;
    cin >> t;
    while (t--) {
        int x, y, v;
        cin >> x >> y >> v;
        wall[x][y] = v;
    }

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, -INF));
    dp[1][1] = a[1][1];
    int ans = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (wall[i][j] <= i + j - 2)
                continue;
            if (j > 1 && dp[i][j - 1] != -INF) {
                dp[i][j] = max(dp[i][j], dp[i][j - 1] + a[i][j]);
            }
            if (i > 1 && dp[i - 1][j] != -INF) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j] + a[i][j]);
            }

            ans = max(ans, dp[i][j]);
        }
    }

    cout << ans << endl;
}

4. 复杂度分析

时间复杂度：
- 预处理墙体信息： $O(t)$ ，其中 $t \le n \times m$ 。
- 动态规划遍历： $O(n \times m)$ 。
- 总复杂度： $O(n \times m)$ 。对于 $1000 \times 1000$ 的规模，计算量约为 $10^6$ ，完全符合 1 秒以内的执行要求。
空间复杂度：
- 墙体时间矩阵： $O(n \times m)$ 。
- DP 状态矩阵： $O(n \times m)$ 。
- 优化空间：由于 $dp[i][j]$ 仅依赖于其左侧和上方的值，可利用“滚动数组”技术将 DP 的空间复杂度降低至 $O(m)$ 。