最长数对链的变种：带权值的最长数对链

题目描述
给定一个由数对组成的数组pairs，其中每个数对pairs[i] = [left_i, right_i]表示一个区间，且left_i < right_i。每个数对还有一个权值weight_i。我们需要找到一个数对链，使得：

1. 链中的每个数对j都在前一个数对i的右边，即right_i < left_j
2. 链的长度尽可能长
3. 在满足长度最长的前提下，链的总权值最大

解题思路
这个问题是最长数对链问题的变种，在标准的动态规划解法基础上增加了权值维度。我们需要同时考虑链的长度和权值。

解题步骤

步骤1：预处理数组
首先对数对数组进行排序，按照每个数对的右端点进行升序排列。这样排序后，当我们考虑当前数对时，只需要关注它前面的数对。

# 示例输入
pairs = [[1,2], [2,3], [3,4], [1,3]]
weights = [1, 2, 3, 4]

# 按照右端点排序
sorted_pairs = sorted(zip(pairs, weights), key=lambda x: x[0][1])

步骤2：定义动态规划状态
我们需要定义两个DP数组：

• length[i]：以第i个数对结尾的最长链的长度
• max_weight[i]：以第i个数对结尾的、长度为length[i]的链的最大权值和

n = len(pairs)
length = [1] * n      # 每个数对本身至少可以形成长度为1的链
max_weight = [0] * n  # 存储对应权值

# 初始化：每个数对单独成链
for i in range(n):
    max_weight[i] = weights[i]

步骤3：状态转移方程
对于每个数对i，我们检查所有在它前面的数对j：

• 如果pairs[j][1] < pairs[i][0]（即j的右端点小于i的左端点）
• 那么我们可以尝试将i接在j后面

状态转移需要考虑三种情况：

1. 如果接上j后链的长度更长，直接更新
2. 如果链的长度相同但权值更大，更新权值
3. 如果链的长度相同但权值更小，保持不变

for i in range(n):
    for j in range(i):
        if sorted_pairs[j][0][1] < sorted_pairs[i][0][0]:  # 满足链条件
            if length[j] + 1 > length[i]:
                # 情况1：可以形成更长的链
                length[i] = length[j] + 1
                max_weight[i] = max_weight[j] + sorted_pairs[i][1]
            elif length[j] + 1 == length[i]:
                # 情况2：链长度相同，选择权值更大的
                if max_weight[j] + sorted_pairs[i][1] > max_weight[i]:
                    max_weight[i] = max_weight[j] + sorted_pairs[i][1]

步骤4：寻找最终答案
我们需要在整个DP数组中寻找：

1. 首先找到最长的链长度
2. 在所有最长链中，找到权值最大的

max_len = max(length) if length else 0
result = 0

for i in range(n):
    if length[i] == max_len:
        result = max(result, max_weight[i])

步骤5：优化（二分查找）
对于大规模输入，O(n²)的时间复杂度可能过高。我们可以使用二分查找来优化：

import bisect

# 存储每个长度对应的最小右端点和最大权值
tails = []  # 每个元素是(右端点, 权值)
dp = [0] * n

for i in range(n):
    left, right = sorted_pairs[i][0]
    weight = sorted_pairs[i][1]
    
    # 二分查找可以接在哪个链后面
    pos = bisect.bisect_left(tails, left, key=lambda x: x[0])
    
    if pos == 0:
        # 不能接在任何链后面，自己作为新链
        current_len = 1
        current_weight = weight
    else:
        # 接在pos-1对应的链后面
        current_len = pos  # tails中索引为pos-1对应的链长度
        current_weight = dp[tails[pos-1][1]] + weight
    
    dp[i] = current_weight
    
    if current_len > len(tails):
        # 形成了更长的链
        tails.append((right, i))
    elif current_len <= len(tails) and current_weight > dp[tails[current_len-1][1]]:
        # 更新当前长度的最优解
        tails[current_len-1] = (right, i)

完整代码示例

def findMaxWeightChain(pairs, weights):
    if not pairs:
        return 0
    
    # 合并并排序
    combined = list(zip(pairs, weights))
    combined.sort(key=lambda x: x[0][1])
    
    n = len(combined)
    length = [1] * n
    max_weight = [w for _, w in combined]
    
    for i in range(n):
        for j in range(i):
            if combined[j][0][1] < combined[i][0][0]:
                if length[j] + 1 > length[i]:
                    length[i] = length[j] + 1
                    max_weight[i] = max_weight[j] + combined[i][1]
                elif length[j] + 1 == length[i]:
                    if max_weight[j] + combined[i][1] > max_weight[i]:
                        max_weight[i] = max_weight[j] + combined[i][1]
    
    max_len = max(length)
    result = 0
    for i in range(n):
        if length[i] == max_len:
            result = max(result, max_weight[i])
    
    return result

# 测试示例
pairs = [[1,2], [2,3], [3,4], [1,3]]
weights = [1, 2, 3, 4]
print(findMaxWeightChain(pairs, weights))  # 输出：6（链：[1,2]→[3,4]，权值1+3=4；但[2,3]权值2，最长链长度为2）

这个算法的时间复杂度为O(n²)，空间复杂度为O(n)。通过二分查找优化可以将时间复杂度降为O(n log n)。