算法提高 夺宝奇兵 显示标签 时间限制：C/C++ 1000MS，其他语言 2000MS 内存限制：C/C++ 512MB，其他语言 1024MB 难度：提高 分数：100 OI排行榜得分：18(0.1*分数+2*难度) 出题人： 描述 在一座山上,有很多很多珠宝,它们散落在山底通往山顶的每条道路上,不同道路上的珠宝的数目也各不相同.下图为一张藏宝地图: 7 　　3 8 　　8 1 0 　　2 7 4 4 　　4 5 2 6 5 ”夺宝奇兵”从山下出发,到达山顶,如何选路才能得到最多的珠宝呢?在上图所示例子中,按照5->7->8->3->7的顺序,将得到最大值30 输入描述 第一行正整数N(100>=N>1),表示山的高度 　　接下来有N行非负整数,第i行有i个整数(1<=i<=N),表示山的第i层上从左到右每条路上的珠宝数目 输出描述 一个整数,表示从山底到山顶的所能得到的珠宝的最大数目. 用例输入 1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 用例输出 1 30 来源 蓝桥杯练习系统C++

以下是解决该“夺宝奇兵”问题的 C++ 代码： ```cpp #include <iostream> #include <algorithm> using namespace std; const int MAXN = 105; int a[MAXN][MAXN]; // 存储每一层每条路上的珠宝数目 int dp[MAXN][MAXN]; // 动态规划数组 int main() { int n; cin >> n; // 输入每一层的珠宝数目 for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { cin >> a[i][j]; } } // 初始化动态规划数组的最后一行 for (int j = 1; j <= n; j++) { dp[n][j] = a[n][j]; } // 从倒数第二层开始向上递推 for (int i = n - 1; i >= 1; i--) { for (int j = 1; j <= i; j++) { // 状态转移方程：当前位置的最大珠宝数等于当前位置的珠宝数加上下一层相邻两个位置的最大珠宝数 dp[i][j] = a[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1]); } } // 输出从山底到山顶所能得到的珠宝的最大数目 cout << dp[1][1] << endl; return 0; } ``` 代码解释： 1. 输入处理： - 首先读取山的高度 `n`。 - 然后使用两层循环读取每一层每条路上的珠宝数目，并存储在二维数组 `a` 中。 2. 动态规划数组初始化： - 将动态规划数组 `dp` 的最后一行初始化为 `a` 数组的最后一行，因为从最后一层到最后一层的最大珠宝数就是该位置的珠宝数。 3. 状态转移： - 从倒数第二层开始向上递推，对于每一个位置 `(i, j)`，其最大珠宝数等于当前位置的珠宝数 `a[i][j]` 加上下一层相邻两个位置 `(i + 1, j)` 和 `(i + 1, j + 1)` 的最大珠宝数中的较大值。 4. 输出结果： - `dp[1][1]` 即为从山底到山顶所能得到的珠宝的最大数目，将其输出。 复杂度分析： - 时间复杂度：$O(n^2)$，其中 $n$ 是山的高度。需要遍历每一层的每一个位置。 - 空间复杂度：$O(n^2)$，主要用于存储动态规划数组。 [2026-02-03 17:13:24 | AI问答 | 649点数解答]