P15717 [JAG 2023 Summer Camp #2] Disjoint-Sparse-Table Optimization

给定一个长度为 $2Q - 1$ 的整数序列 $A$，以及 $Q$ 个区间 $[L_i, R_i)$。其中，$L_i, R_i$ 满足 $L_i < R_i$，并且 $1$ 到 $2Q$ 之间的每个整数都恰好作为某个区间的端点出现一次。 你的目标是创建一个区间集合 $S$，使得对于所有 $i = 1, 2, \ldots, Q$，至少满足以下条件之一： - $[L_i, R_i) \in S$ - 存在一个整数 $x$（$L_i < x < R_i$），使得 $[L_i, x) \in S$ 且 $[x, R_i) \in S$。 集合 $S$ 的代价定义如下： - 对于 $S$ 中包含的所有区间 $[l, r)$，计算 $A_l + A_{l+1} + \ldots + A_{r-1}$ 的总和。 求满足条件的最小代价。

$$ \begin{aligned} &Q \\ &L_1 \ R_1 \\ &\vdots \\ &L_Q \ R_Q \\ &A_1 \ A_2 \ \ldots \ A_{2Q-1} \end{aligned} $$ 输入满足以下约束： - 所有输入均为整数。 - $1 \leq Q \leq 100$ - $1 \leq L_i < R_i \leq 2Q$ - $1$ 到 $2Q$ 之间的每个整数都出现在 $L_1, \ldots, L_Q, R_1, \ldots, R_Q$ 中。 - $1 \leq A_i \leq 10^9$

输出满足条件的最小代价。

在样例输入 1 中，最优集合为 $S = \{[1, 4), [2, 3), [3, 5), [5, 6)\}$，其代价为 $6 + 2 + 7 + 5 = 20$。 翻译由 DeepSeek V3.2 完成