首页 > 试题广场 >

工作安排

[编程题]工作安排

热度指数：2280 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美是团队的负责人，需要为团队制定工作的计划，以帮助团队产出最大的价值。

每周团队都会有两项候选的任务，其中一项为简单任务，一项为复杂任务，两项任务都能在一周内完成。第i周，团队完成简单任务的价值为l_i，完成复杂任务的价值为h_i。由于复杂任务本身的技术难度较高，团队如果在第i周选择执行复杂任务的话，需要在i-1周不做任何任务专心准备。如果团队在第i周选择执行简单任务的话，不需要提前做任何准备。

现在小美的团队收到了未来N周的候选任务列表，请帮助小美确定每周的工作安排使得团队的工作价值最大。

输入描述:

第一行为N（0≤N≤1000）

接下来的N行表示第1到N周两项候选任务的价值，第i行的格式为：l_i h_i，其中 0 < l_i < 10000, 0< h_i < 10000。

输出描述:

输出一个数字，表示小美团队在未来N周能产出的最大价值。

示例1

输入

输出

算法知识视频讲解

Python

牛客318213606号

# 我的解法：17/20 组用例通过。。。
# 因为这题有个坑: 第1周既可以做简单任务也可以做复杂任务，而我之前的理解是第1周只能做简单任务，因为没有前一周的准备时间啊
# 但这题默认在第一周前已经可以做好充分准备
def run(ls,hs):
    n=len(ls)#n=len(hs)
    #dp[i]:未来第i周能够获得的最大工作价值,i=1,2,...,n
    dp=[0 for _ in range(n+1)]
    # dp[0]无意义

    # (~~划掉~~)初始化：第0周没有准备时间，所以只能选择做简单任务
    # 初始化：第1周可以选择直接做复杂任务，也可以做简单任务
    dp[1]=max(ls[0],hs[0])

    # 从第2周开始，按照正常逻辑计算。。。
    for i in range(2,n+1):
        # 可以选择做简单任务：dp[i]=dp[i-1]+ls[i]
        # 也可以选择做复杂任务(需要提前一周准备，此时前一周啥也不做，)：dp[i]=dp[i-2]+hs[i]
        dp[i]=max(dp[i-1]+ls[i-1], dp[i-2]+hs[i-1])

    return dp[n]

while True:
    try:
        n=int(input())

        if n==0:
            print(0)
            continue

        ls,hs=[],[]
        for _ in range(n):
            cur_l,cur_h=map(int,input().split(' '))
            ls.append(cur_l)
            hs.append(cur_h)

        if n==1:
            print(ls[0])
            continue

        res=run(ls,hs)
        print(res)
    except:
        break

发表于 2022-06-11 21:37:19 回复(0)

Python

小橙子&

本题其实在初始值设置上有点小问题，难道一开始就可以进行难工作？不需要缓冲期？若是考虑开始不能做难工作，通过率只有85%，程序不考虑缓冲期，则通过率100%

N = int(input().strip(' '))
data = []
for _ in range(N):
    cur = [int(i) for i in input().strip(' ').split(' ')]
    data.append(cur)
dp = [[0] * (N+1) for _ in range(2)]
dp[0][1] = data[0][0]
#这里考虑了开始能做难工作的情况
dp[1][1] = data[0][1]
for i in range(2,N+1):
    dp[0][i] = data[i-1][0] + max(dp[0][i-1],dp[1][i-1])
    dp[1][i] = data[i-1][1] + max(dp[0][i-2],dp[1][i-2])
print(max(dp[0][-1],dp[1][-1]))

编辑于 2020-08-21 16:55:38 回复(0)

Python

张学友学编程

为什么通过百分之95，还差什么？

n=int(input())
s=[]
res=[0]*n
for i in range(n):
    inp=list((map(int,input().split(' '))))
    s.append(inp)
res[0]=max(s[0])
res[1]=max(res[0]+s[1][0],s[1][1])
for i in range(2,n):
    res[i]=max(res[i-1]+s[i][0],res[i-2]+s[i][1])
print(res[-1])

发表于 2020-08-20 15:16:38 回复(2)