题解 | #合唱队#

合唱队

https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4

这个思路就是对每一个位置上的元素先找它左边的增序列,再找它右边的减序列,同时记录下最长的长度,最后用总人数减去最大的人数就可以了。

这段代码是正确可运行的,就是复杂度太高了,我用自己的编辑器可以得到所有正确答案,就是超时,一点优化的思路是压缩循环,直接遍历全元素的dp增序列和减序列

n = int(input())
talls = list(map(int, input().split()))


if n < 3:
    print(0)
else:
    members = 0
    for i in range(1, n - 1):
        dpl = [0] * (i + 1)
        for il in range(1, i + 1):
            for j in range(0, il):
                if talls[il] > talls[j]:
                    dpl[il] = max(dpl[il], dpl[j] + 1)
        dpr = [0] * n
        for ir in range(n - 2, i - 1, -1):
            for k in range(n - 1, ir, -1):
                if talls[ir] > talls[k]:
                    dpr[ir] = max(dpr[ir], dpr[k] + 1)

        if dpl[i] != 0 and dpr[i] != 0:
            members = max(dpl[i] + dpr[i] + 1, members)
    print(n - members)
全部评论

相关推荐

07-02 13:50
闽江学院 Java
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务