当前位置：首页 > 培训职业 > 正文

2024牛客暑期多校训练营2 I Red Playing Cards

设区间的位置分别是 [公式]

设区间 [公式] 消除区间 [公式] 的最大值

在数组头尾添加 [公式] ，最终答案是 [公式] 。

如何计算 [公式] ？

区间和与其相交区间互斥，一个区间仅由包含它的区间更新，如下图所示。

设 [公式] := 对于元素 [公式] 的区间，消除 [公式] 的最大值

因此，[公式] = [公式] + [公式] （加上两端点的值）

从左往右遍历区间 [公式] ，当遍历 [公式] 号虚线处时，只由元素 [公式] 更新： [公式]

当遍历 [公式] 处，考虑 [公式] 这段由元素 [公式] 或 [公式] 最优，并更新只更新右端点 [公式] ： [公式]

当遍历 [公式] 处，元素 [公式] 和 [公式] 交叉，更新 [公式] ： [公式]

发现转移方程由左端点[公式] 转移，未受 [公式] 影响，选择 [公式] 不影响 [公式] ，满足互斥。

最后确保内部小区间最优，从大到小枚举元素。

总结：转移方程如下：

对于元素[公式] 的区间：

[公式]

代码实现：（省略）