CF1456E.XOR-ranges

给定整数 $c_{0}, c_{1}, \ldots, c_{k-1}$，我们可以定义一个数 $0 \le x < 2^{k}$ 的代价为 $p(x) = \sum_{i=0}^{k-1} \left( \left\lfloor \frac{x}{2^{i}} \right\rfloor \bmod 2 \right) \cdot c_{i}$。换句话说，数 $x$ 的代价等于 $x$ 的所有二进制位中为 $1$ 的位所对应的 $c_{i}$ 之和。

我们定义长度为 $n \ge 2$、元素取自区间 $[0, 2^{k})$ 的数组 $a$ 的代价如下：$cost(a) = \sum_{i=1}^{n - 1} p(a_{i} \oplus a_{i+1})$，其中 $\oplus$ 表示按位异或运算。

现在给定每个元素的取值范围：$l_{i} \le a_{i} \le r_{i}$，请你构造一个长度为 $n$ 的数组，使其代价最小。

第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 50$，$1 \le k \le 50$），分别表示数组的长度和数字的二进制位数。

接下来的 $n$ 行，每行包含两个整数 $l_{i}$ 和 $r_{i}$（$0 \le l_{i} \le r_{i} < 2^{k}$），表示第 $i$ 个元素的取值范围。

最后一行包含 $c_{0}, c_{1}, \ldots, c_{k-1}$（$0 \le c_{i} \le 10^{12}$）。

输出一个整数，表示满足所有限制条件的数组的最小代价。

在第一个样例中，只有一个数组满足所有限制条件——$[3, 5, 6, 1]$，其代价为 $cost([3, 5, 6, 1]) = p(3 \oplus 5) + p(5 \oplus 6) + p(6 \oplus 1) = p(6) + p(3) + p(7) = (c_{1} + c_{2}) + (c_{0} + c_{1}) + (c_{0} + c_{1} + c_{2}) = (2 + 7) + (5 + 2) + (5 + 2 + 7) = 30$。

在第二个样例中，唯一的最优数组是 $[2, 3, 6]$。

由 ChatGPT 4.1 翻译