题解： P13494 【MX-X14-T4】分门别类

前景描述

这是本蒟蒻第一次写题解，请多多照顾

问题重述

我们需要帮助Yuki在提瓦特大陆的方格图中完成她的旅程。她可以从第1行的任意一个方格开始，每次可以向左、向右或向下移动（在前n-1行时），到达第n行时旅程结束。移动过程中，摩拉数量会根据所在方格的数值变化，且不能为负，也不能超过k。我们需要判断是否能完成旅程，并求出完成时的最大摩拉数量。

思路

1.定义状态

设 $ dp[i][j] $ 表示到达方格 $ (i,j) $ 时的最大摩拉数量。我们的目标是通过动态规划填充这个表格，最终在第 $ n $ 行找到最大的 $ dp[n][j] $。

2. 初始条件

Yuki从第1行的某个方格开始，初始摩拉数量为 $ s $。因此，对于第1行的每个方格 $ (1,j) $，初始摩拉数量为：

[ dp[1][j] = \min(\max(s + a[1][j], 0), k) ]

如果 $ s + a[1][j] < 0 $，则 $ dp[1][j] = -1 $（表示不可达）。

3. 状态转移

对于每个方格 $ (i,j) $，可以从三个方向移动而来：

1. 从上方 $ (i-1,j) $： $new_val = dp[i-1][j] + a[i][j]$
2. 从左侧 $ (i,j-1) $（如果 $ j > 1 $）： $new_val = dp[i][j-1] + a[i][j]$
3. 从右侧 $ (i,j+1) $（如果 $ j < m $）： $new_val = dp[i][j+1] + a[i][j]$

对于每个方向，更新 $ dp[i][j] $ 为：

$ dp[i][j] = \min(\max(\text{new_val}, 0), k) $

如果 $ \text{new_val} < 0 $，则不更新 $ dp[i][j] $。

4. 边界条件

• 第1行的初始化如上述。
• 对于第 $ n $ 行，只能从上方或左右移动而来，且不能再移动。

5. 最终结果

遍历第 $ n $ 行的所有 $ dp[n][j] $，取最大值。如果所有 $ dp[n][j] $ 都为 -1，则输出 -1。

代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

void solve() {
    int c, T;
    cin >> c >> T;
    while (T--) {
        int n, m, s, k;
        cin >> n >> m >> s >> k;
        vector<vector<int>> grid(n, vector<int>(m));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cin >> grid[i][j];
            }
        }

        vector<vector<int>> dp(n, vector<int>(m, -1));
        queue<pair<int, int>> q;

        // Initialize first row
        for (int j = 0; j < m; ++j) {
            int val = s + grid[0][j];
            if (val < 0) continue;
            if (val > k) val = k;
            dp[0][j] = val;
            q.push({0, j});
        }

        // Directions: down, left, right
        int dirs[3][2] = {{1, 0}, {0, -1}, {0, 1}};

        while (!q.empty()) {
            auto [i, j] = q.front();
            q.pop();
            for (auto [di, dj] : dirs) {
                int ni = i + di;
                int nj = j + dj;
                if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
                int new_val = dp[i][j] + grid[ni][nj];
                if (new_val < 0) continue;
                if (new_val > k) new_val = k;
                if (new_val > dp[ni][nj]) {
                    dp[ni][nj] = new_val;
                    q.push({ni, nj});
                }
            }
        }

        int max_mora = -1;
        for (int j = 0; j < m; ++j) {
            if (dp[n-1][j] > max_mora) {
                max_mora = dp[n-1][j];
            }
        }
        cout << max_mora << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

这是本蒟蒻第一次写正式题解，恳求审核大大通过qwq