题目描述 话说孙悟空取经的途中曾遇到一座大山，大山上有很多宝藏，当然了，妖怪也是在所难免的，此山能大能小，最高不过50米，最宽嘛也不过40米而已，此山是通往西天取经的必经之路，山上有很多的宝藏，宝藏都位于洞穴之中，你路过洞穴，就能获得宝藏，当然了，你遇到妖怪之后还要上交过路费，当宝藏大于等于0的时候，你就能获得它，当少于0的时候，说明洞穴中存在妖怪，你要上交过路费了，宝藏最大不超过100块，不小于-100块；小猴子是打不过他们的，因为他没有了72变，你要想问为什么，这个、、、 PS：此时的你位于左山脚下，你的任务就是到达山顶最右端，并取得最大的价值，以供在以后的路上开销，此山特别的神奇，当你每上升一层的时候，你的下面就全部自动消失了，当你每向右走一层的时候，你的左面也全部自动消失了； 输入 输入： 开始先输入一个T，表示下面有T组数据； 接下来会有T组测试用例，每组数组第一行有两个数x，y，分别表示山的高和山的宽； 接下来有x行，每行有y个数；第一行表示最上面一层，第二行最上面的下面一层、、、最后一行表示最底层； 输出 输出T组数据，每组数据表示猴子所能获得的最大的金钱数； 样例输

以下是解决该问题的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点数解答]