题解 | #收集金币#

1. 问题分析

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

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

关键点：到达时间计算 在 的网格中，从 出发，到达任意位置 所需的步数（即移动回合数）是固定的。由于每回合只能向下或向右移动一格，到达 的总步数 始终满足： 因此，玩家在第 回合动作结束后到达 。

2. 算法：动态规划

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

可通行性判定准由： 根据题目描述，每一回合开始时方格先变化。玩家从 到达 的移动发生在第 个回合。

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

状态定义： 设 表示到达方格 时能收集到的最大金币数。

状态转移方程： 对于每个位置 ：

1. 判定是否为墙：如果已知 在第 回合变墙，且 （且 ），则该点不可达，标记为 。
2. 正常转移：若非墙，则： 注意：需处理边界情况，若上方和左方均不可达，则当前点亦不可达。

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. 复杂度分析

• 时间复杂度：

  • 预处理墙体信息：，其中 。
  • 动态规划遍历：。
  • 总复杂度：。对于 的规模，计算量约为 ，完全符合 1 秒以内的执行要求。

• 空间复杂度：

  • 墙体时间矩阵：。
  • DP 状态矩阵：。
  • 优化空间：由于 仅依赖于其左侧和上方的值，可利用“滚动数组”技术将 DP 的空间复杂度降低至 。