首页 > 试题广场 >

假期

[编程题]假期

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

由于业绩优秀，公司给小Q放了 n 天的假，身为工作狂的小Q打算在在假期中工作、锻炼或者休息。他有个奇怪的习惯：不会连续两天工作或锻炼。只有当公司营业时，小Q才能去工作，只有当健身房营业时，小Q才能去健身，小Q一天只能干一件事。给出假期中公司，健身房的营业情况，求小Q最少需要休息几天。

输入描述:

第一行一个整数  表示放假天数
第二行 n 个数 每个数为0或1,第 i 个数表示公司在第 i 天是否营业
第三行 n 个数 每个数为0或1,第 i 个数表示健身房在第 i 天是否营业
（1为营业 0为不营业）

输出描述:

一个整数，表示小Q休息的最少天数

示例1

输入

4
1 1 0 0
0 1 1 0

输出

说明

小Q可以在第一天工作，第二天或第三天健身，小Q最少休息2天

算法知识视频讲解

Python

myyhdmz

动态规划，每一天有三种状态

day = int(input())
com = list(map(int, input().split()))
gym = list(map(int, input().split()))

dp = [0 for i in range(3)]

for i in range(day):
    tmp = [day for i in range(3)]
    # 工作
    if com[i]:
        tmp[0] = min(dp[1], dp[2])
    # 锻炼
    if gym[i]:
        tmp[1] = min(dp[0], dp[2])
    # 休息
    tmp[2] = min(dp[0], dp[1], dp[2]) + 1
    dp = tmp

print(min(dp))

发表于 2020-11-26 11:11:39 回复(0)

Python

牛客699525022号

day=int(input())
_C=input()
c=[int(i) for i in _C.split()]
_G=input()
g=[int(i) for i in _G.split()]
 
a=[c.copy(),g.copy()]
 
for i in range(day-1):
    if c[i]==0:
        a[0][i+1]+=a[0][i] if a[0][i] > a[1][i] else a[1][i]
    else:
        a[0][i+1]+=a[1][i]
    if g[i]==0:
        a[1][i+1]+=a[0][i] if a[0][i] > a[1][i] else a[1][i]
    else:
        a[1][i+1]+=a[0][i]
 
print(day-(a[0][day-1] if a[0][day-1]>a[1][day-1] else a[1][day-1]))

a[:][i]表示到第i天为止已经工作或运动的天数。

编辑于 2020-07-02 17:37:04 回复(0)