冲浪 - 动态规划算法求解最大快乐值

冲浪：动态规划算法求解最大快乐值

冲浪大师睿睿打算冲浪 'n' 分钟，每分钟内他可以选择一朵浪花冲上去站 '1' 分钟，站满 '1' 分钟后，这朵浪花就会消散于大海中，睿睿需要换一朵浪花，否则他就会掉进海里。

最开始有 'm' 朵浪花，就算睿睿不站上去，浪花会在某个时刻自然消散，第 'i' 朵浪花会在第 'a_i' 分钟结束时消散。每朵浪花能带给睿睿的快乐是不同的，站在第 'i' 朵浪花上会给睿睿带来 'b_i' 的快乐。

如果睿睿掉进了海里，那么他之前获得的快乐都会消失，他需要从 '0' 开始重新积累快乐。

求睿睿 'n' 分钟结束时的最大快乐值。

输入格式

从标准输入读入数据。 第一行输入两个正整数 'n'（'n ≤ 500'）和 'm'（'m ≤ 2000'）。 第二行输入 'm' 个正整数 'a_i'（'a_i ≤ n'）。 第三行输入 'm' 个正整数 'b_i'（'b_i ≤ 1000'）。

输出格式

输出到标准输出。 输出一个整数，表示最大快乐值。

样例 #1

样例输入 #1

6 8
4 2 6 2 6 1 1 6
13 14 5 7 4 3 8 1

样例输出 #1

45

提示

样例1解释

一种最优的浪花安排为（浪花的格式为 '(a_i, b_i)'）：

'(1, 8)', '(2, 14)', '(6, 1)', '(4, 13)', '(6, 4)', '(6, 5)'

这是一个经典的动态规划问题，可以使用动态规划求解。

首先，我们定义一个状态数组 'dp'，'dp[i]' 表示在第 'i' 分钟结束时可以获得的最大快乐值。

然后，我们可以通过遍历所有的浪花，更新状态数组 'dp'。对于每一朵浪花 '(a_i, b_i)'，我们可以选择站在上面或者不站在上面。如果选择站在上面，那么在第 'a_i' 分钟结束时，我们可以获得 'b_i' 的快乐值，加上之前 'a_i' 分钟内积累的最大快乐值 'dp[i - a_i]'，得到第 'i' 分钟结束时的最大快乐值。如果选择不站在上面，那么第 'i' 分钟结束时的最大快乐值就是之前 'i - 1' 分钟结束时的最大快乐值 'dp[i - 1]'。我们取这两种情况中的最大值作为 'dp[i]' 的值。

最后，我们返回 'dp[n]'，即第 'n' 分钟结束时的最大快乐值。

下面是具体的实现代码：

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

dp = [0] * (n + 1)  # 初始化状态数组

for i in range(1, n + 1):
    dp[i] = dp[i - 1]  # 不站在浪花上的情况

    for j in range(m):
        if i >= a[j]:
            dp[i] = max(dp[i], dp[i - a[j]] + b[j])  # 站在浪花上的情况

print(dp[n])  # 输出最大快乐值

该实现的时间复杂度为 'O(n * m)'，空间复杂度为 'O(n)'，其中 'n' 是冲浪时间，'m' 是浪花数量。