A6147. 「USACO 2024.2 Platinum」Minimum Sum of Maximums
编程题
NOI/NOI+/CTSC
知识点
题目描述
**题目来自 [USACO 2024 February Contest, Platinum](http://usaco.org/index.php?page=feb24results) Problem 2. [Minimum Sum of Maximums](http://usaco.org/index.php?page=viewproblem2&cpid=1405)**
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<\ldots <x_K\le N$）的瓷砖。
Bessie 想要最小化瓷砖的总丑陋度，其中总丑陋度定义为每对相邻瓷砖的最大丑陋度之和；即 $\sum_{i=1}^{N-1} \max(a_i,a_{i+1})$。她可以任意次执行以下操作：选择两块均未卡住的瓷砖，并交换它们。
求 Bessie 以最优方案执行操作可以达到的最小总丑陋度。
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<\ldots <x_K\le N$）的瓷砖。
Bessie 想要最小化瓷砖的总丑陋度，其中总丑陋度定义为每对相邻瓷砖的最大丑陋度之和；即 $\sum_{i=1}^{N-1} \max(a_i,a_{i+1})$。她可以任意次执行以下操作：选择两块均未卡住的瓷砖，并交换它们。
求 Bessie 以最优方案执行操作可以达到的最小总丑陋度。
输入格式
输入的第一行包含 $N$ 和 $K$。
第二行包含 $a_1,\ldots ,a_N$。
第三行包含 $K$ 个索引 $x_1,\ldots ,x_K$。
第二行包含 $a_1,\ldots ,a_N$。
第三行包含 $K$ 个索引 $x_1,\ldots ,x_K$。
输出格式
输出最小可能的总丑陋度。
输入输出样例
输入 #1
3 0 1 100 10
输出 #1
110
输入 #2
3 1 1 100 10 3
输出 #2
110
输入 #3
3 1 1 100 10 2
输出 #3
200
输入 #4
4 2 1 3 2 4 2 3
输出 #4
9
说明/提示
- 测试点 5：$K=0$。
- 测试点 6-7：$K=1$。
- 测试点 8-12：$N\le 50$。
- 测试点 13-24：没有额外限制。
供题：Benjamin Qi
- 测试点 6-7：$K=1$。
- 测试点 8-12：$N\le 50$。
- 测试点 13-24：没有额外限制。
供题：Benjamin Qi