首页 > 试题广场 >

瞌睡

[编程题]瞌睡
  • 热度指数:34288 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小易觉得高数课太无聊了,决定睡觉。不过他对课上的一些内容挺感兴趣,所以希望你在老师讲到有趣的部分的时候叫醒他一下。你知道了小易对一堂课每分钟知识点的感兴趣程度,并以分数量化,以及他在这堂课上每分钟是否会睡着,你可以叫醒他一次,这会使得他在接下来的k分钟内保持清醒。你需要选择一种方案最大化小易这堂课听到的知识点分值。

输入描述:
第一行 n (1 <= n <= 105), k (0 <= k <= 105) ,表示这堂课持续多少分钟,以及叫醒小易一次使他能够保持清醒的时间。
第二行 n 个数,a1, a2, ... , an(1 <= a<= 104) 表示小易对每分钟知识点的感兴趣评分。
第三行 n 个数,t1, t2, ... , tn 表示每分钟小易是否清醒, 1表示清醒。


输出描述:
小易这堂课听到的知识点的最大兴趣值。
示例1

输入

6 3
1 3 5 2 5 4
1 1 0 1 0 0

输出

16

前缀和

很简单,用两个前缀和数组配合一下就可以了。是知识点数组的前缀和,是知识点数组在考虑小易是否清醒时的前缀和。

然后枚举叫醒小易的时机,遍历小易的精神状态数组,如果当前分钟为0,就尝试“课堂叫醒服务”,时间段内利用数组计算区间和,其余时段用数组计算区间和即可。
if __name__ == "__main__":
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    t = list(map(int, input().split()))
    p1, p2 = [0] * n, [0] * n      # 不考虑、考虑t状态的前缀和
    p1[0] = a[0]
    p2[0] = a[0] if t[0] else 0
    for i in range(1, n):
        p1[i] = p1[i - 1] + a[i]
        p2[i] = p2[i - 1] + a[i] if t[i] else p2[i - 1]
    if k == 0&nbs***bsp;sum(t) == n:
        print(p2[-1])       # 叫不醒或者没有睡觉的时候就直接返回
    else:
        ans = 0
        for i in range(n):
            if t[i] == 0:
                if i == 0:
                    ans = max(ans, p1[k - 1] + p2[-1] - p2[k - 1])
                else:
                    if i + k - 1 < n:
                        ans = max(ans, p2[i - 1] + (p1[i + k - 1] - p1[i - 1]) + p2[n - 1] - p2[i + k - 1])
                    else:
                        ans = max(ans, p2[i - 1] + p1[-1] - p1[i - 1])
                        
        print(ans)

发表于 2022-04-11 15:49:25 回复(0)