题解：P10229 [COCI 2023/2024 #4] Knjige

· · 题解

题目简化：

给定 n 本书，每本书的吸引力为 k_i，以及两个时间参数 a 和 b，分别表示阅读一本书的全部时间和仅看封面所需的时间。定义灵感值为完整阅读的书籍吸引力的总和。问题转化为在给定时间 t 内，如何最大化灵感值。

解题思路：

首先，我们需要确定阅读方式：要么完整阅读，要么只看封面。由于灵感值与完整阅读的书的吸引力有关，我们的目标是在时间 t 内尽可能多地阅读吸引力大的书。

设 f(i) 表示在时间 t 内从第 1 本书开始阅读到第 i 本书时的最大可能灵感值。为了计算 f(i)，我们考虑两种情况：

如果选择完整阅读第 i 本书，则需要花费 a 分钟，灵感值增加 k_i。这种情况下的灵感值为 f(i)=k_i+f(i-1)。
如果选择只看第 i 本书的封面，则需要花费 b 分钟，而灵感值不变。这种情况下的灵感值为 f(i)=f(i-1)。最终结果应当为 f(n)。

现在，我们有一个递推式，可以通过动态规划解决问题。由于每次阅读都会增加时间消耗，我们可以从最大的时间消耗开始，逐步减少，直到时间不足以完成当前书的阅读。在这个过程中，我们记录下每个时间点对应的最大灵感值。

具体实现时，可以使用一个一维数组 dp 来存储每个状态的灵感值，其中 dp_i 表示阅读前 i 本书的最大可能灵感值。然后，从前往后遍历所有书，对于每一本书，我们都尝试以两种方式阅读它，并更新 dp 数组。

最后，dp_n 中存储的就是我们要求的最大灵感值。

提示：

  1. 这个算法的时间复杂度为 O(n)，空间复杂度也为 O(n)。
  2. 这1题可以优化空间使用，只用一个一维数组来存储当前状态和上一个状态的灵感值，即 dp_i=\max(dp_i,dp_i-1+k_i)。