以下是解决该问题的C++代码： ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; // 函数用于计算最大价值 int maxValue(vector<vector<int>>& mountain) { int x = mountain.size(); int y = mountain[0].size(); // 创建一个二维数组dp来存储到达每个位置的最大价值 vector<vector<int>> dp(x, vector<int>(y, 0)); // 初始化dp数组的第一个元素 dp[0][0] = mountain[0][0]; // 初始化第一行，因为只能从左边到达 for (int j = 1; j < y; ++j) { dp[0][j] = dp[0][j - 1] + mountain[0][j]; } // 初始化第一列，因为只能从上面到达 for (int i = 1; i < x; ++i) { dp[i][0] = dp[i - 1][0] + mountain[i][0]; } // 填充dp数组的其余部分 for (int i = 1; i < x; ++i) { for (int j = 1; j < y; ++j) { // 选择从上面或左边到达当前位置的最大价值 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + mountain[i][j]; } } // 返回到达山顶最右端的最大价值 return dp[x - 1][y - 1]; } int main() { int T; cin >> T; while (T--) { int x, y; cin >> x >> y; // 创建一个二维数组来存储山的信息 vector<vector<int>> mountain(x, vector<int>(y, 0)); // 读取山的信息 for (int i = 0; i < x; ++i) { for (int j = 0; j < y; ++j) { cin >> mountain[i][j]; } } // 计算最大价值 int result = maxValue(mountain); // 输出结果 cout << result << endl; } return 0; } ``` 代码解释 1. 输入处理：首先读取测试用例的数量`T`，然后对于每个测试用例，读取山的高度`x`和宽度`y`，并读取山的每个位置的宝藏或过路费信息。 2. 动态规划数组`dp`：创建一个二维数组`dp`，其中`dp[i][j]`表示到达位置`(i, j)`的最大价值。 3. 初始化`dp`数组：初始化`dp[0][0]`为起点的宝藏或过路费，然后初始化第一行和第一列，因为只能从左边或上面到达。 4. 填充`dp`数组：对于其余位置`(i, j)`，选择从上面或左边到达的最大价值加上当前位置的宝藏或过路费。 5. 输出结果：返回`dp[x - 1][y - 1]`，即到达山顶最右端的最大价值。 额外注意的逻辑点 1. 边界条件处理：在初始化第一行和第一列时，要确保只考虑从左边或上面到达的情况，避免越界访问。 2. 状态转移方程：在填充`dp`数组时，要正确选择从上面或左边到达的最大价值，以确保得到最优解。 3. 输入的合法性：要确保输入的山的高度和宽度在规定范围内，避免数组越界。 [2025-06-14 21:01:48 | AI写代码神器 | 862点数解答]