题目描述
Bessie 有一行 $N$（$2\le N\le 300$）块瓷砖，依次具有丑陋度 $a_1,a_2,\ldots,a_N$（$1\le a_i\le 10^6$）。其中 $K$（$0\le K\le \min(N,6)$）块瓷砖卡住了；具体地，索引为 $x_1,\ldots,x_K$（$1\le x_1<x_2<\cdots<x_K\le N$）的瓷砖。
Bessie 想要最小化瓷砖的总丑陋度，其中总丑陋度定义为每对相邻瓷砖的最大丑陋度之和；即 $\sum\limits^{N−1}{i=1}\max(a_i,a{i+1})$。她可以任意次执行以下操作：选择两块均未卡住的瓷砖，并交换它们。
求 Bessie 以最优方案执行操作可以达到的最小总丑陋度。
输入格式
输入的第一行包含 $N$ 和 $K$。
第二行包含 $a_1,\ldots,a_N$。
第三行包含 $K$ 个索引 $x_1,\ldots,x_K$。
输出格式
输出最小可能的总丑陋度。
输入输出样例 #1
输入 #1
1 | |
输出 #1
1 | |
输入输出样例 #2
输入 #2
1 | |
输出 #2
1 | |
输入输出样例 #3
输入 #3
1 | |
输出 #3
1 | |
说明/提示
样例解释 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\le 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 \le a_R$。
性质一：$a_{L+1},\cdots, 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$ 的段的最小贡献。
由上面的填数过程可知，我们不会在内部的小段留一些数给外面更大的段。（调整法也可以证明）
因此，设 $len_S$ 表示集合为 $S$ 的段的长度之和，满足 $f(l,r,S)$ 最小且 $r - l + 1$ 最小的 $l, r$ 一定满足 $r - l + 1 = len_S$。
考虑三种状态转移：
- 目前左边/右边的数留给下一个包住它的段，$f(l,r,S) = \min\set{f(l+1,r,S), f(l,r-1,S)}$，这部分转移是 $O(1)$ 的，复杂度等于状态数 $O(2^K n^2)$。
- 把两端拼起来，考虑枚举子集，$f(l,r,S)$ 可以从 $f(l,l+len_S-1,S')+ f(r-len_{S-S'}+1,r,S-S')$ 转移过来，复杂度为 $O(3^K n^2)$。
- 用一个大段包住中间的小段，$f(l,r,S)$ 可以从 $f(l+1,r-1,S-\set{x}) + F_x(a_l, a_r)$，其中 $F_x(a_l, a_r)$ 表示第 $x$ 段最小值为 $a_l$ 最大值为 $a_r$ 的贡献，这部分由于用大段包住小段的时候一定满足 $r - l + 1 = len_S$，所以复杂度为 $O(n2^K K)$。
最后复杂度为 $O(3^K n^2)$，瓶颈为第二种转移。
