Minimum Sum of Maximums

题目描述

Bessie 有 $N$（$2\le N\le 300$）块排成一行的瓷砖，按顺序的丑陋值为 $a_1, a_2, \dots, a_N$（$1\le a_i\le 10^6$）。其中有 $K$（$0\le K\le \min(N,6)$）块瓷砖被固定在原位；具体来说，是下标为 $x_1,\dots, x_K$（$1\le x_1 < x_2<\dots< x_K\le 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$。

输出格式

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

3 0
1 100 10

110

3 1
1 100 10
3

110

3 1
1 100 10
2

200

4 2
1 3 2 4
2 3

9

提示

Bessie 可以交换第二块和第三块瓷砖，使得 $a=[1,10,100]$，从而得到总丑陋值 $\max(1,10)+\max(10,100)=110$。或者，她也可以交换第一块和第二块瓷砖，使得 $a=[100,1,10]$，同样得到总丑陋值 $\max(100,1)+\max(1,10)=110$。 Bessie 可以交换第一块和第二块瓷砖，使得 $a=[100,1,10]$，从而得到总丑陋值 $\max(100,1)+\max(1,10)=110$。 瓷砖初始的总丑陋值为 $\max(1,100)+\max(100,10)=200$。 Bessie 只允许交换第一块和第三块瓷砖，这无法让她降低总丑陋值。 计分： 输入 5：$K=0$ 输入 6-7：$K=1$ 输入 8-12：$N\le 50$ 输入 13-24：无额外限制 题目作者：Benjamin Qi

标签: USACO|2024|Platinum

来源

USACO|2024|Platinum