带权值的最长数对链
字数 2208 2025-12-07 08:10:17

带权值的最长数对链

题目描述
给定 n 个数对，其中每个数对 (a, b) 满足 a < b。我们定义一条“数对链”为一系列数对 (a1, b1), (a2, b2), …, (ak, bk)，其中对于所有 1 ≤ i < k，有 bi < ai+1（即后一个数对的第一个元素大于前一个数对的第二个元素）。每个数对还有一个权值 wi。目标是找到一条数对链，使得链中数对的权值之和最大。你需要输出最大的权值和。

例如，数对为 [(1,2,3), (2,3,5), (3,4,2)]，其中每个三元组表示 (a, b, w)。可能链有：

  • 单独 (1,2,3)：权值和 3
  • 单独 (2,3,5)：权值和 5
  • 单独 (3,4,2)：权值和 2
  • (1,2,3) -> (3,4,2)：因为 2 < 3 满足，权值和 3+2=5
  • (2,3,5) 无法与 (3,4,2) 连接，因为 3 不小于 3。
    最大权值和为 5（来自单独 (2,3,5) 或链 (1,2,3)->(3,4,2)）。

解题过程

  1. 问题理解与预处理
    题目本质是选择数对构成序列，要求相邻数对满足 b_i < a_j。由于数对顺序可任意排列，我们应先按数对的第一个元素 a 排序（或按第二个元素 b 排序）。常见思路是按第一个元素 a 升序排序，这样在动态规划时，我们只需考虑前面的数对能否接在当前数对之前。但需要注意：因为连接条件是 b_i < a_j，所以如果按 a 排序，不能保证前面的数对 b 一定小于当前的 a，因此我们仍需逐一检查。

  2. 定义状态
    设 dp[i] 表示以第 i 个数对为结尾的链的最大权值和。排序后，数对编号 1 到 n。最终答案是 max(dp[i]) 对所有 i，因为最优链可能以任意数对结尾。

  3. 状态转移方程
    对于每个 i，我们看前面所有 j (1 ≤ j < i) 是否满足 b_j < a_i。如果满足，则我们可以将数对 i 接在数对 j 的链后面，形成更长的链，此时权值和为 dp[j] + w_i。如果不满足，则数对 i 只能自己作为链的开头，权值和为 w_i。因此：
    dp[i] = max( w_i, max{ dp[j] + w_i | 对所有 j < i 且 b_j < a_i } )
    注意：即使没有 j 满足条件，dp[i] 至少是 w_i（单独成链）。

  4. 初始化
    dp[i] 初始可设为 w_i，因为每个数对至少可以自己成为链。

  5. 计算顺序
    由于我们按 a 升序排序，对于每个 i，我们需要检查所有 j < i 是否满足 b_j < a_i。这是一个双重循环，时间复杂度 O(n²)。在 n 较大时可能较慢，但这是基础动态规划解法。

  6. 边界情况

    • 如果所有数对的 a 都相等，则由于连接条件 b_j < a_i 几乎不可能满足（因为 b_j > a_j = a_i，所以 b_j < a_i 不成立），此时每个数对只能独立，答案就是 max(w_i)。
    • 如果所有数对都满足 b_j < a_i 对任意 j < i，那么我们可以贪心地连接，但动态规划仍能正确处理。

  7. 优化考虑
    为了加速，我们可以先按 b 排序（或按 a 排序后用二分查找优化）。但这里我们先实现基础 O(n²) 版本，因为更直观。

  8. 示例演算
    数对：[(1,2,3), (2,3,5), (3,4,2)]，按 a 排序后顺序不变。

    • i=1: dp[1] = w1 = 3
    • i=2: 检查 j=1: b1=2, a2=2，不满足 2<2，所以没有可接的，dp[2] = w2 = 5
    • i=3: 检查 j=1: b1=2, a3=3，满足 2<3，候选 dp[1]+w3=3+2=5；
      检查 j=2: b2=3, a3=3，不满足 3<3；
      取 max(w3=2, 5) = 5。
      最终 max(dp[1], dp[2], dp[3]) = max(3,5,5) = 5。

  9. 算法实现思路

    1. 将所有数对按第一个元素 a 升序排序（如果 a 相同，可以按 b 升序，但通常不影响正确性）。
    2. 初始化 dp 数组，长度为 n，dp[i] = w_i。
    3. 对于 i 从 0 到 n-1：
      对于 j 从 0 到 i-1：
      如果 pairs[j].b < pairs[i].a：
      dp[i] = max(dp[i], dp[j] + w_i)
    4. 返回 max(dp)。

  10. 进一步优化（选讲）
    如果 n 很大（如 10^5），O(n²) 会超时。我们可以用线段树或树状数组优化：

    • 将所有数对的 b 和 a 离散化。
    • 按 a 升序处理，对于当前数对 i，我们需要查询所有 b < a_i 的数对中最大的 dp 值，这可以用树状数组维护前缀最大值。
    • 处理完数对 i 后，将其 dp[i] 更新到树状数组的 b_i 位置（如果 b_i 相同，可能需要取较大值）。
      这样复杂度可降至 O(n log n)。

总结
本题是“最长数对链”的加权版本，从最长链长度变为最大权值和。核心是排序后动态规划，状态 dp[i] 表示以 i 结尾的最大权值和，转移时检查前面所有可接的数对。基础解法 O(n²)，可用数据结构优化到 O(n log n)。

带权值的最长数对链 题目描述 给定 n 个数对，其中每个数对 (a, b) 满足 a < b。我们定义一条“数对链”为一系列数对 (a1, b1), (a2, b2), …, (ak, bk)，其中对于所有 1 ≤ i < k，有 bi < ai+1（即后一个数对的第一个元素大于前一个数对的第二个元素）。每个数对还有一个权值 wi。目标是找到一条数对链，使得链中数对的权值之和最大。你需要输出最大的权值和。 例如，数对为 [ (1,2,3), (2,3,5), (3,4,2) ]，其中每个三元组表示 (a, b, w)。可能链有： 单独 (1,2,3)：权值和 3 单独 (2,3,5)：权值和 5 单独 (3,4,2)：权值和 2 (1,2,3) -> (3,4,2)：因为 2 < 3 满足，权值和 3+2=5 (2,3,5) 无法与 (3,4,2) 连接，因为 3 不小于 3。 最大权值和为 5（来自单独 (2,3,5) 或链 (1,2,3)->(3,4,2)）。 解题过程 问题理解与预处理 题目本质是选择数对构成序列，要求相邻数对满足 b_ i < a_ j。由于数对顺序可任意排列，我们应先按数对的第一个元素 a 排序（或按第二个元素 b 排序）。常见思路是 按第一个元素 a 升序排序 ，这样在动态规划时，我们只需考虑前面的数对能否接在当前数对之前。但需要注意：因为连接条件是 b_ i < a_ j，所以如果按 a 排序，不能保证前面的数对 b 一定小于当前的 a，因此我们仍需逐一检查。 定义状态 设 dp[ i] 表示以第 i 个数对为结尾的链的最大权值和。排序后，数对编号 1 到 n。最终答案是 max(dp[ i ]) 对所有 i，因为最优链可能以任意数对结尾。 状态转移方程 对于每个 i，我们看前面所有 j (1 ≤ j < i) 是否满足 b_ j < a_ i。如果满足，则我们可以将数对 i 接在数对 j 的链后面，形成更长的链，此时权值和为 dp[ j] + w_ i。如果不满足，则数对 i 只能自己作为链的开头，权值和为 w_ i。因此： dp[ i] = max( w_ i, max{ dp[ j] + w_ i | 对所有 j < i 且 b_ j < a_ i } ) 注意：即使没有 j 满足条件，dp[ i] 至少是 w_ i（单独成链）。 初始化 dp[ i] 初始可设为 w_ i，因为每个数对至少可以自己成为链。 计算顺序 由于我们按 a 升序排序，对于每个 i，我们需要检查所有 j < i 是否满足 b_ j < a_ i。这是一个双重循环，时间复杂度 O(n²)。在 n 较大时可能较慢，但这是基础动态规划解法。 边界情况 如果所有数对的 a 都相等，则由于连接条件 b_ j < a_ i 几乎不可能满足（因为 b_ j > a_ j = a_ i，所以 b_ j < a_ i 不成立），此时每个数对只能独立，答案就是 max(w_ i)。 如果所有数对都满足 b_ j < a_ i 对任意 j < i，那么我们可以贪心地连接，但动态规划仍能正确处理。 优化考虑 为了加速，我们可以先按 b 排序（或按 a 排序后用二分查找优化）。但这里我们先实现基础 O(n²) 版本，因为更直观。 示例演算 数对：[ (1,2,3), (2,3,5), (3,4,2) ]，按 a 排序后顺序不变。 i=1: dp[ 1 ] = w1 = 3 i=2: 检查 j=1: b1=2, a2=2，不满足 2<2，所以没有可接的，dp[ 2 ] = w2 = 5 i=3: 检查 j=1: b1=2, a3=3，满足 2<3，候选 dp[ 1 ]+w3=3+2=5； 检查 j=2: b2=3, a3=3，不满足 3 <3； 取 max(w3=2, 5) = 5。 最终 max(dp[ 1], dp[ 2], dp[ 3 ]) = max(3,5,5) = 5。 算法实现思路 将所有数对按第一个元素 a 升序排序（如果 a 相同，可以按 b 升序，但通常不影响正确性）。 初始化 dp 数组，长度为 n，dp[ i] = w_ i。 对于 i 从 0 到 n-1： 对于 j 从 0 到 i-1： 如果 pairs[ j].b < pairs[ i ].a： dp[ i] = max(dp[ i], dp[ j] + w_ i) 返回 max(dp)。 进一步优化（选讲） 如果 n 很大（如 10^5），O(n²) 会超时。我们可以用线段树或树状数组优化： 将所有数对的 b 和 a 离散化。 按 a 升序处理，对于当前数对 i，我们需要查询所有 b < a_ i 的数对中最大的 dp 值，这可以用树状数组维护前缀最大值。 处理完数对 i 后，将其 dp[ i] 更新到树状数组的 b_ i 位置（如果 b_ i 相同，可能需要取较大值）。 这样复杂度可降至 O(n log n)。 总结 本题是“最长数对链”的加权版本，从最长链长度变为最大权值和。核心是排序后动态规划，状态 dp[ i ] 表示以 i 结尾的最大权值和，转移时检查前面所有可接的数对。基础解法 O(n²)，可用数据结构优化到 O(n log n)。