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}$ 有关，与其他位置的值无关。

TODO