Dream__Sky @ 2024-09-16 22:01:43
这题有
by yanglee2 @ 2024-09-16 22:07:58
要解决这个问题，我们可以用动态规划来处理。我们需要维护一个状态来表示当前时间点的最大愉悦值，同时考虑到不能连续打相同的项目超过 ( m ) 分钟。
思路和步骤 定义状态:
dp[i][0]: 在第 i 分钟时，且第 i 分钟是 florr 的情况下的最大愉悦值。 dp[i][1]: 在第 i 分钟时，且第 i 分钟是模拟赛的情况下的最大愉悦值。 状态转移:
如果 i 分钟是 florr, 可以从 i-1 分钟是 florr 转移过来，或者从模拟赛转过来。对应的状态转移公式需要根据当前的连续时间 t 来计算。 如果 i 分钟是模拟赛, 同理可以从 i-1 分钟是模拟赛转移过来，或者从 florr 转过来。 初始化:
dp[0][0] 和 dp[0][1] 的初始值为 0，因为我们从第 0 分钟开始，没有前导值。 计算总分数:
使用滑动窗口或者其他方法来计算在某个时间段内的总分数，并用其计算愉悦值。 结果:
遍历所有 dp 状态，找出最大愉悦值，同时保证分数不低于 k。 复杂度 这个动态规划的方法时间复杂度为 (O(n \cdot m))，每分钟需要处理 m 分钟的窗口情况。空间复杂度也是 (O(n \cdot m)) 以保存状态。 这种方法的主要挑战在于如何有效地处理和更新状态，以及如何通过窗口滑动来保证分数条件。通过实现这种 DP 解法，我们可以在 (O(n \log n)) 的复杂度下找到最大愉悦值。
by Dream__Sky @ 2024-09-16 22:14:17
@yanglee2 别用GPT啊