简答题 偏难
#19329

巧夺大奖 时间限制:1.0 s 内存限制:128.0 MB 问题描述 小明参加了一个巧夺大奖的游戏节目。主持人宣布了游戏规则: 1、游戏分为n个时间段,参加者每…

巧夺大奖

时间限制:1.0 s

内存限制:128.0 MB


问题描述

小明参加了一个巧夺大奖的游戏节目。主持人宣布了游戏规则:

1、游戏分为n个时间段,参加者每个时间段可以选择一个小游戏。

2、游戏中共有n个小游戏可供选择。

3、每个小游戏有规定的时限和奖励。对于第i个小游戏,参加者必须在第Ti个时间段结束前完成才能得到奖励Ri。

小明发现,这些小游戏都很简单,不管选择哪个小游戏,他都能在一个时间段内完成。关键问题在于,如何安排每个时间段分别选择哪个小游戏,才能使得总奖励最高?

输入描述

输入第一行,包含一个正整数n。 既是游戏时间段的个数,也是小游戏的个数。约定1≤n≤500。

输入第二行,包含n个正整数。第i个正整数为Ti,即第i个小游戏的完成期限。约定1≤Ti≤n。

输入第三行,包含n个正整数。第i个正整数为Ri,即第i个小游戏的完成奖励。约定1≤Ri≤1000。

 输出描述

输出一行,包含一个正整数C,为最高可获得的奖励。


样例输入1

7

4 2 4 3 1 4 6

70 60 50 40 30 20 10

样例输出1

230

样例解释1

7个时间段可分别安排完成第4、2、3、1、6、7、5个小游戏,其中第4、2、3、1、7个小游戏在期限内完成。因此,可以获得总计40+60+50+70+10=230的奖励。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:python;toolbar:false">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] &gt;= 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 &lt; 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)</pre><p><br/></p>
这道题暂未补解析。