算法提高 夺宝奇兵 显示标签 时间限制：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++

这是一个典型的动态规划问题，解题的关键在于从山顶到山底进行状态转移，逐步计算出到达每一个位置能获得的最大珠宝数。 以下是使用 Python 实现的代码： ```python # 读取输入的山的高度 n = int(input()) # 初始化一个二维列表 dp 来存储到达每个位置能获得的最大珠宝数 dp = [] # 循环读取每一行的珠宝数目 for i in range(n): row = list(map(int, input().split())) dp.append(row) # 从倒数第二行开始向上遍历 for i in range(n - 2, -1, -1): for j in range(i + 1): # 状态转移方程：当前位置的最大珠宝数等于当前位置的珠宝数加上下方两个位置中能获得的最大珠宝数 dp[i][j] += max(dp[i + 1][j], dp[i + 1][j + 1]) # 山顶位置（即 dp[0][0]）存储的就是从山底到山顶能获得的最大珠宝数 print(dp[0][0]) ``` 代码解释： 1. 输入处理：首先读取山的高度 `n`，然后逐行读取每一层的珠宝数目，并将其存储在二维列表 `dp` 中。 2. 动态规划：从倒数第二行开始向上遍历，对于每一个位置 `(i, j)`，更新其最大珠宝数为当前位置的珠宝数加上下方两个位置中能获得的最大珠宝数。 3. 输出结果：最终，山顶位置 `dp[0][0]` 存储的就是从山底到山顶能获得的最大珠宝数，将其输出。 复杂度分析： - 时间复杂度：$O(n^2)$，其中 $n$ 是山的高度。需要遍历二维列表中的每一个元素。 - 空间复杂度：$O(n^2)$，主要用于存储二维列表 `dp`。 [2026-02-03 17:12:35 | AI问答 | 456点数解答]