1.11 bilibili 2024校招笔试真题

1.11.1 漫展打卡奖励

【题目描述】

某次漫展，已知有n个打卡点，每个打卡点的活动需要 m_i 分钟完成，完成后获得奖励点 r_i，已经打卡过的点不能再去。

需要在规定 m 分钟内完成，尽可能多的收获奖励点，求获得最多的奖励点数。

输入描述：

第一行两个整数，打卡点的数量 n 和限制时间 m

第 2 到 1 + n 行，每行两个整数 m_i，r_i

数字以空格分割，其中 0 < n <= 100，1 <= m <= 120，1 <= m_i <= 10，1 <= r_i <= 100

输出描述：

整数, 最大的奖励点数

输入样例：

4 6

2 4

2 35

1 43

2 10

输出样例：

88

【解题思路】

01背包问题

【参考代码】

import sys

n, m = map(int, sys.stdin.readline().strip().split(" "))

points = []

for i in range(n):

m_i, r_i = map(int, sys.stdin.readline().strip().split(" "))

points.append([m_i, r_i])

#print(points)

# dp[i][j]: 当前已考虑i之前的所有点，剩余时间为j时的得分

dp = [[0]*(m+1) for _ in range(n+1)]

for i in range(1, n+1):

for j in range(1, m+1):

# 剩余时间不足

m_i, r_i = points[i-1][0], points[i-1][1]

if j < m_i:

dp[i][j] = dp[i-1][j]

else:

dp[i][j] = max(dp[i-1][j], dp[i-1][j - m_i] + r_i)

print(dp[n][m])

1.11.2 整数转罗马数字

【题目描述】

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符 数值

I 1

V 5

X 10

L 50

C 100

D 500

M 1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X