题解 | #合唱队#

合唱队

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)
全部评论

相关推荐

点赞 评论 收藏
分享
MinJerous:虽然我一直说 计算机不怎么卡学历 但是至少得一本
点赞 评论 收藏
分享
Yki_:你要算时间成本呀,研究生两三年,博士三四年,加起来就五六年了,如果你本科去腾讯干五年,多领五年的年薪,加上公司内涨薪,可能到时候十五年总薪资也跟博士差不多
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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