离散化权值在数据处理中的应用与实现

CF960F 题解：动态规划与树状数组的巧妙结合

问题背景

CF960F（Codeforces 960F）是一道经典的动态规划问题，题目名为"Pathwalks"，给定一个有向图，每条边有编号和权值，要求找到一条路径，使得路径中边的编号严格递增且权值严格递增，求满足条件的路径的更大长度。

问题分析

• 输入：图的边按顺序给出，每条边包含起点、终点、编号和权值。
• 约束条件：路径的边编号和权值必须严格递增。
• 目标：更大化路径长度（边的数量）。

解题思路

动态规划（DP）：
定义 dp[i][w] 表示以编号为 i、权值为 w 的边结尾的路径的更大长度，状态转移方程为：

dp[i][w] = max(dp[j][w']) + 1，j < i 且 w' < w。

直接暴力转移时间复杂度为 O(n²)，无法通过大规模数据。

优化：树状数组（Fenwick Tree）

• 将权值离散化,用树状数组维护前缀更大值。
• 对边按编号排序后,依次处理每条边，用树状数组查询权值小于当前边的更大 dp 值，更新当前边的 dp 状态。
• 时间复杂度优化至 O(n log n)。

代码实现（伪代码）

rank = {v: i+1 for i, v in enumerate(sorted_weights)}
# 初始化树状数组
fenwick = FenwickTree(max_rank)
for edge in edges:
    u, v, num, w = edge
    # 查询权值小于w的更大dp值
    max_len = fenwick.query(rank[w] - 1)
    # 更新当前边的dp值
    fenwick.update(rank[w], max_len + 1)
result = fenwick.query(max_rank)

CF960F 通过动态规划与树状数组的结合，高效解决了二维偏序问题，关键在于：

1. 按编号顺序处理边,保证编号递增。
2. 用树状数组维护权值维度上的前缀更大值,避免重复计算。

此题的思维难度和代码实现技巧对算法竞赛选手具有很好的训练价值。

延伸思考：类似问题可扩展到更高维度的偏序约束，例如结合时间、空间等多维条件的更优化路径问题。