首页 > [0820]顺丰笔试python版本(租服务器+赏金猎人)
头像
NeilYU
编辑于 2020-08-20 22:12
+ 关注

[0820]顺丰笔试python版本(租服务器+赏金猎人)

第一题直接AC没占出来…
第二题,结束时间排序+dp
python版本,结尾时间排序做

class mission:
    def __init__(self, l, r, w):
        self.l, self.r, self.w = l, r, w

def main():
    n = int(input())
    if n < 1: return 0
    M = []
    for _ in range(n):
        l, r, w = map(int, input().split())
        M.append(mission(l, r, w))

    # 按结束时间升序排列
    M.sort(key=lambda x: x.r)

    front = [-1 for _ in range(n)]  # 与第i个任务相容的前一个任务编号
    for i in range(n - 1, 0, -1):
        for j in range(i - 1, -1, -1):
            if M[j].r < M[i].l: #这里有个坑,前一个任务的r必须小于后一个任务的l
                front[i] = j
                break

    dp = [0 for _ in range(n)]  # 以第i个任务结尾的最大收益
    dp[0] = M[0].w
    for i in range(1,n):
        if front[i]>=0:
            dp[i] = max(dp[i - 1], dp[front[i]] + M[i].w)
        else:
            dp[i]=max(dp[i-1],M[i].w)

    return dp[-1]


print(main())


全部评论

(3) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐