A36280. 巧夺大奖问题描述小明参加了一个巧夺大奖的游戏节目。主持人宣布了游戏规则：1、游戏分为 个时间段，参加者每个时间段可以选择一个小游戏。2、游戏中共有 个小游戏可供选择。3、每个小游戏有规定的时限和奖励。对于第 个小游戏，参加者必须在第 个时间段结束前完成才能得到奖励 。小明发现，这些小游戏都很简单，不管选择哪个小游戏，他都能在一个时间段内完成。关键问题在于，如何安排每个时间段分别选择哪个小游戏，才…
填空题
困难
知识点
题目描述
巧夺大奖
问题描述
小明参加了一个巧夺大奖的游戏节目。主持人宣布了游戏规则：
1、游戏分为 个时间段，参加者每个时间段可以选择一个小游戏。
2、游戏中共有 个小游戏可供选择。
3、每个小游戏有规定的时限和奖励。对于第 个小游戏，参加者必须在第 个时间段结束前完成才能得到奖励 。
小明发现，这些小游戏都很简单，不管选择哪个小游戏，他都能在一个时间段内完成。关键问题在于，如何安排每个时间段分别选择哪个小游戏，才能使得总奖励最高？
输入描述
输入第一行，包含一个正整数n。 既是游戏时间段的个数，也是小游戏的个数。约定 1<=n<=500。
输入第二行，包含n个正整数。第 i 个正整数为 Ti，即第 i 个小游戏的完成期限。约定 1<=Ti<=n。
输入第三行，包含n个正整数。第 i 个正整数为 Ri，即第 i 个小游戏的完成奖励。约定 1<=Ri<=100。
输出描述
输出一行，包含一个正整数C，为最高可获得的奖励。
样例输入1
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10样例输出1
230参考答案
total_segements = int(input())
limits = []
rewards = []
s_limits = input()
s_limits = s_limits.split(' ')
s_rewards = input()
s_rewards = s_rewards.split(" ")
for item in s_limits:
limits.append(int(item))
for item in s_rewards:
rewards.append(int(item))
games = []
for i in range(len(s_limits)): #结束时间， 奖励值， 是否可以选， 是否选过
games.append([limits[i], rewards[i], False, False])
def check_chooseable(states, current):
for item in states:
if item[0] >= current:
item[2] = True
def get_current_max(states, current):
maximum = 0
chosen = None
for i in range(len(states)):
if states[i][2] and not states[i][3]:
if maximum < states[i][1]: #print(states[i][1])
maximum = max(states[i][1], maximum)
chosen = i
if chosen is not None:
states[chosen][3] = True
return maximum
total = 0# print(games)
for t in range(total_segements, 0, -1): #print(t)
check_chooseable(games, t)
total += get_current_max(games, t)# print(games)
print(total)
上一题
下一题