洛谷P6786题解：数学与算法结合的子序列优化

1. 题目解析与核心思路拆解

这道P6786题目来自洛谷8月月赛，属于典型的数学与算法结合题型。题目要求从给定序列中选出一个子序列，满足特定条件并使元素和最大化。我们先拆解题目核心条件：

对于选出的每个元素b_i，必须满足以下两个条件之一：

1. 它是子序列中的最大值
2. 存在另一个元素b_j > b_i，且满足b_i + b_j + gcd(b_i,b_j) = lcm(b_i,b_j)

这个看似复杂的条件实际上隐藏着数学规律。通过数学推导可以发现，当两个数满足x + y + gcd(x,y) = lcm(x,y)时，这两个数必须满足特定的倍数关系。经过推导可以得出，这对数必须是(k, k*(k+1))的形式，其中k是正整数。

例如：

• k=1时：1和2（1+2+1=4=2）
• k=2时：2和6（2+6+2=10=6）
• k=3时：3和12（3+12+3=18=12）

2. 算法设计与优化策略

2.1 暴力解法分析

最直观的解法是枚举所有可能的子序列，检查条件并计算最大和。但这种方法时间复杂度为O(2^n)，对于n≤3×10^5的数据规模完全不适用。

2.2 关键观察与优化

通过数学分析我们发现，有效的数对必须满足倍数关系。因此可以得出以下结论：

1. 子序列中的数必须形成一个"链式"结构，其中每个数要么是最大值，要么是某个更大数的"前驱"
2. 这种结构类似于树形关系，其中较大的数可以"包含"较小的符合条件的数

基于此，我们可以设计一个动态规划解法：

1. 对数组进行排序
2. 使用哈希表记录每个数作为链尾时的最大和
3. 对于每个数a_i，检查所有可能的k使得k*(k+1)=a_i，并更新哈希表

2.3 具体算法步骤

1. 输入处理：读取n和数组a
2. 数组排序：将a从小到大排序
3. 初始化哈希表dp：key为数值，value为以该数结尾的子序列最大和
4. 遍历处理：
   • 对于每个a_i，初始dp[a_i] = a_i
   • 找出所有满足k*(k+1)=a_i的k值
   • 对于每个有效k，更新dp[a_i] = max(dp[a_i], dp[k] + a_i)
5. 结果输出：dp中的最大值

3. C++实现详解

3.1 完整代码实现

cpp复制#incl