美团算法方向编程题《工作安排》dp不能通过,求助大佬们
小美是团队的负责人,需要为团队制定工作的计划,以帮助团队产出最大的价值。
每周团队都会有两项候选的任务,其中一项为简单任务,一项为复杂任务,两项任务都能在一周内完成。第i周,团队完成简单任务的价值为 li,完成复杂任务的价值为 hi。由于复杂任务本身的技术难度较高,团队如果在第 i 周选择执行复杂任务的话,需要在 i-1 周不做任何任务专心准备。如果团队在第 i 周选择执行简单任务的话,不需要提前做任何准备。
现在小美的团队收到了未来N周的候选任务列表,请帮助小美确定每周的工作安排使得团队的工作价值最大。
输入:
第一行为N(0≤N≤1000) 接下来的N行表示第1到N周两项候选任务的价值,第i行的格式为:li hi,其中li > 0, hi > 0,都为float型。
输出:
小美团队在未来N周能产出的最大价值
样例输入:
4 10.0 5.0 1.0 50.1 10.0 5.0 10.0 1.0样例输出:
70.1提示:
说明:第一周准备,第二周执行复杂任务,第三周和第四周执行简单任务,价值为0 + 50.1 + 10 + 10 = 70.1动态规划(通过27%):
while 1: N = int(input()) dp = [0.0]*(N+2) for i in range(N): l, h = list(map(float, input().split())) dp[i+2] = max(dp[i+1]+l, dp[i]+h) print(dp[-1])如果限制第一周必须执行简单任务,通过率45%。