P10197 [USACO24FEB] Minimum Sum of Maximums P

题目描述

Bessie 有一行 $N$ （ $2 \leq N \leq 300$ ）块瓷砖，依次具有丑陋度 $a_{1}, a_{2}, \dots, a_{N}$ （ $1 \leq a_{i} \leq 10^{6}$ ）。其中 $K$ （ $0 \leq K \leq min (N, 6)$ ）块瓷砖卡住了；具体地，索引为 $x_{1}, \dots, x_{K}$ （ $1 \leq x_{1} < x_{2} < \dots < x_{K} \leq N$ ）的瓷砖。

Bessie 想要最小化瓷砖的总丑陋度，其中总丑陋度定义为每对相邻瓷砖的最大丑陋度之和；即 $\sum_{i = 1}^{N - 1} max (a_{i}, a_{i + 1})$ 。她可以任意次执行以下操作：选择两块均未卡住的瓷砖，并交换它们。

求 Bessie 以最优方案执行操作可以达到的最小总丑陋度。

输入格式

输入的第一行包含 $N$ 和 $K$ 。

第二行包含 $a_{1}, \dots, a_{N}$ 。

第三行包含 $K$ 个索引 $x_{1}, \dots, x_{K}$ 。

输出格式

输出最小可能的总丑陋度。

输入输出样例 #1

输入 #1

1 2	`3 0 1 100 10`

输出 #1

输入输出样例 #2

输入 #2

1
2
3

3 1
1 100 10
2

输出 #2

输入输出样例 #3

输入 #3

1
2
3

4 2
1 3 2 4
2 3

输出 #3

说明/提示

样例解释 1

Bessie 可以交换第二块和第三块瓷砖，使得 $a = [1, 10, 100]$ ，达到总丑陋度 $max (1, 10) + max (10, 100) = 110$ 。或者，她也可以交换第一块和第二块瓷砖，使得 $a = [100, 1, 10]$ ，同样达到总丑陋度 $max (100, 1) + max (1, 10) = 110$ 。

样例解释 2

瓷砖的初始总丑陋度为 $max (1, 100) + max (100, 10) = 200$ 。Bessie 只允许交换第一块和第三块瓷砖，这并不能使她能够减少总丑陋度。

测试点性质

测试点 $5$ ： $K = 0$ 。
测试点 $6 - 7$ ： $K = 1$ 。
测试点 $8 - 12$ ： $N \leq 50$ 。
测试点 $13 - 24$ ：没有额外限制。

题解

性质分析

考虑到未固定的数可以任意交换，本题可转化为： $K$ 个数被固定在数列中，将剩余 $N - K$ 个数放到其余位置，使得总丑陋值最小。

丑陋值可表示为：

\sum_{i = 1}^{n - 1} max (a_{i}, a_{i + 1}) = \sum_{i = 1}^{n - 1} \frac{1}{2} (a_{i} + a_{i + 1} + \abs a_{i} - a_{i + 1})

其中 $\sum_{i = 1}^{n - 1} \frac{1}{2} (a_{i} + a_{i + 1})$ 是固定值，因此题目目标是最小化 $\sum_{i = 1}^{n - 1} \abs a_{i} - a_{i + 1}$ 。为了便于处理，我们在数列中加入 $a_{0} = a_{n + 1} = inf$ 。

$K$ 个被固定的数将原序列分为至多 $K + 1$ 段，我们分别处理每一段 $[a_{L}, a_{R}]$ ，其中 $L < R$ 且 $a_{L}, a_{R}$ 已经被固定。不妨设 $a_{L} \leq a_{R}$ 。

性质一： $a_{L + 1}, \dots, a_{R - 1}$ 序列应该单增，这样使得 $[a_{L}, a_{R}]$ 段的总贡献最小（如果 $a_{L} > a_{R}$ ，这里应该是单减）。

可以用调整法证明这一结论。

在性质一的安排下， $[a_{L}, a_{R}]$ 的总贡献为 $\abs a_{L} - a_{L - 1} + \abs a_{R} - a_{R - 1} + a_{R - 1} - a_{L + 1}$ 。该贡献仅与 $a_{L + 1}, a_{R - 1}$ 有关，与其他位置的值无关。显然这两个数分别是区间内的最大值和最小值，我们用 $min_{i}, max_{i}$ 分别表示第 $i$ 个区间 $[a_{L_{i} + 1}, a_{R_{i} - 1}]$ （不含 $a_{L_{i}}, a_{R_{i}}$ ）内的最大值和最小值。

注意到关于 $max_{i}$ 的贡献为 $| a_{R_{i}} - max_{i} ∣ + max_{i}$ 随着 $max_{i}$ 减小单减，关于 $min_{i}$ 的贡献 $| a_{L_{i}} - min_{i} | - min_{i}$ 随着 $min_{i}$ 增大单减。

因此可以通过调整法证明每个区间内的值域区间 $[min_{i}, max_{i}]$ 要么相离要么包含，否则可以把相交区间切成两部分，使得 $max_{i}$ 变小 $min_{j}$ 变大来得到一个更不差的总丑陋值。

DP 方案

填数方案：从小到大考虑每个数，要么它作为某一段的左边界，要么它填入目前左边界最大的没填满的段（若存在多个未填满的段，则这些区间是包含关系，必然要让左边界最大的段右边界最小），此时若将这个段填满了就直接作为这个段右边界。

我们用区间 DP 实现这个填数过程。令 $f (l, r, S)$ 表示下标为 $[l, r]$ 的数已经填满集合为 $S$ 的段的最小贡献。

由上面的填数过程可知，我们不会在内部的小段留一些数给外面更大的段。（调整法也可以证明）

因此，设 $l e n_{S}$ 表示集合为 $S$ 的段的长度之和，满足 $f (l, r, S)$ 最小且 $r - l + 1$ 最小的 $l, r$ 一定满足 $r - l + 1 = l e n_{S}$ 。

考虑三种状态转移：

目前左边/右边的数留给下一个包住它的段， $f (l, r, S) = min {f (l + 1, r, S), f (l, r - 1, S)}$ ，这部分转移是 $O (1)$ 的，复杂度等于状态数 $O (2^{K} n^{2})$ 。
把两端拼起来，考虑枚举子集， $f (l, r, S)$ 可以从 $f (l, l + l e n_{S} - 1, S^{'}) + f (r - l e n_{S - S^{'}} + 1, r, S - S^{'})$ 转移过来，复杂度为 $O (3^{K} n^{2})$ 。
用一个大段包住中间的小段， $f (l, r, S)$ 可以从 $f (l + 1, r - 1, S - {x}) + F_{x} (a_{l}, a_{r})$ ，其中 $F_{x} (a_{l}, a_{r})$ 表示第 $x$ 段最小值为 $a_{l}$ 最大值为 $a_{r}$ 的贡献，这部分由于用大段包住小段的时候一定满足 $r - l + 1 = l e n_{S}$ ，所以复杂度为 $O (n 2^{K} K)$ 。

最后复杂度为 $O (3^{K} n^{2})$ ，瓶颈为第二种转移。