闯关游戏
时间限制：2.0 s
内存限制：128.0 MB
问题描述
你来到了一个闯关游戏。
这个游戏总共有N关，每关都有M个通道，你需要选择一个通道并通往后续关卡。其中，第i个通道可以让你前进ai关，也就是说，如果你现在在第x关，那么选择第i个通道后，你将直接来到第x+ai关（特别地，如果x+ai≥N，那么你就通关了）。此外，当你顺利离开第s关时，你还将获得bs分。
游戏开始时，你在第0关。请问，你通关时最多能获得多少总分？
输入描述
第一行两个整数N,M，分别表示关卡数量和每关的通道数量。
接下来一行M个用单个空格隔开的整数a0,a1,……,aM-1。保证1≤ai≤N。
接下来一行N个用单个空格隔开的整数b0,b1,……,bN-1。保证|bi|≤105。
输出描述
一行一个整数，表示你通关时最多能够获得的分数。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
6 2 2 3 1 0 30 100 30 30
样例输出 1
131
样例解释 1
你可以在第0关选择第1个通道，获得1分并来到第3关；随后再选择第0个通道，获得100分并来到第5关；最后任选一个通道，都可以获得30分并通关。如此，总得分为1+100+30=131。
样例输入 2
6 2 2 3 1 0 30 100 30 -1
样例输出 2
101
样例解释 2
请注意，一些关卡的得分可能是负数。
数据规模
对于20%的测试点，保证M=1。
对于40%的测试点，保证N≤20；保证M≤2。
对于所有测试点，保证N≤104；保证M≤100。
相似题推荐
给定一棵二叉树，采用广度优先搜索(BFS) 算法，返回右视图所有节点的值。其中右视图定义为：二叉树的右视图是从树的右侧看过去时可见的节点集合，即右视图中的每个节点都是某一层中最右侧的节点。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def rightSideView(root):
rightmost_value_at_depth = {}
max_depth = -1
node_queue = []
depth_queue = []
node_queue.append(root)
depth_queue.append(0)
while node_queue:
node = node_queue.pop(0)
depth = depth_queue.pop(0)
if node is not None:
max_depth = max(max_depth, depth)
rightmost_value_at_depth[depth] = node.val
node_queue.append(node.left)
node_queue.append(node.right)
# (1) 填空处
depth_queue.append(depth + 1)
depth_queue.append(depth + 1)
right_view = []
# (2) 填空处
for depth in range(max_depth + 1):
right_view.append(rightmost_value_at_depth[depth])
return right_view
if __name__ == "__main__":
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
root.right.right = TreeNode(4)
print(rightSideView(root))| A． （1）depth , depth ;（2）0 , max_depth |
B． （1）depth + 1 , depth + 1 ;（2）0 , max_depth + 1 |
| C． （1）depth + 1 , depth + 1 ;（2）1 , max_depth + 1 |
D． （1）depth , depth ;（2）1 , max_depth |
游乐园的过山车每次限坐4 人，用循环队列管理排队（容量MAX=5，空一格判满）。下面代码执行后，循环队列是否已满？rear 的值是多少？
MAX = 5
queue = [None] * MAX
front = 0
rear = 0
def enqueue(x):
global rear, queue
queue[rear] = x
rear = (rear + 1) % MAX
def dequeue():
global front
front = (front + 1) % MAX
if __name__ == "__main__":
enqueue(1)
enqueue(2)
enqueue(3)
enqueue(4)
dequeue()
dequeue()
enqueue(5)
enqueue(6)
print("队列数组: ", queue)
print("front下标位置: ", front)
print("rear下标位置: ", rear)| A． 已满，rear = 1 |
B． 未满，rear = 1 |
| C． 已满，rear = 2 |
D． 未满，rear = 4 |
设二叉树共有n个结点，函数 preorderTraversal 的时间复杂度为O(n)，空间复杂度为O(n)。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def preorder(root, res):
if root is None:
return
res.append(root.val)
preorder(root.left, res)
preorder(root.right, res)
def preorderTraversal(root):
res = []
preorder(root, res)
return res
if __name__ == "__main__":
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
result = preorderTraversal(root)
print("前序遍历结果: ", result) | A．正确 | B．错误 |
在二叉搜索树（BST）中，若中序遍历的序列为{1, 2, 3, 4, 5}，且先序遍历的第一个序列元素为3，则下列说法正确的是（）。
| A． 该树一定是一棵完全二叉树。 |
B． 元素4和5不可能是兄弟节点。 |
| C． 元素1所在节点的深度可能大于3（根节点深度为1）。 |
D． 元素2一定是元素1的父节点。 |
