#PU1405. USACO 2024 February Contest, Platinum — Problem 2. Minimum Sum of Maximums

USACO 2024 February Contest, Platinum — Problem 2. Minimum Sum of Maximums

USACO 2024 February Contest, Platinum — Problem 2. Minimum Sum of Maximums

题目描述

Bessie has NN (2≤N≤3002\le N\le 300) tiles in a line with ugliness values a1,a2,…,aNa_1, a_2, \dots, a_N in that order (1≤ai≤1061\le a_i\le 10^6). KK (0≤K≤min⁡(N,6)0\le K\le \min(N,6)) of the tiles are stuck in place; specifically, those at indices x1,…,xKx_1,\dots, x_K (1≤x1<x2<⋯<xK≤N1\le x_1 < x_2<\dots< x_K\le N). Bessie wants to minimize the total ugliness of the tiles, which is defined as the sum of the maximum ugliness over every consecutive pair of tiles; that is, ∑i=1N−1max⁡(ai,ai+1)\sum_{i=1}^{N-1}\max(a_i,a_{i+1}). She is allowed to perform the following operation any number of times: choose two tiles, neither of which are stuck in place, and swap them. Determine the minimum possible total ugliness Bessie can achieve if she performs operations optimally.

输入格式

The first line contains NN and KK. The next line contains a1,…,aNa_1,\dots,a_N. The next line contains the KK indices x1,…,xKx_1,\dots,x_K.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 0
1 100 10
110
Bessie can swap the second and third tiles so that $a=[1,10,100]$, achieving
total ugliness $\max(1,10)+\max(10,100)=110$. Alternatively, she could swap the
first and second tiles so that $a=[100,1,10]$, also achieving  total ugliness
$\max(100,1)+\max(1,10)=110$.

样例 2

3 1
1 100 10
3
110
Bessie could swap the first and second tiles so that $a=[100,1,10]$, achieving 
total ugliness $\max(100,1)+\max(1,10)=110$.

样例 3

3 1
1 100 10
2
200
The initial total ugliness of the tiles is $\max(1,100)+\max(100,10)=200$.
Bessie is only allowed to swap the first and third tiles, which does not allow
her to reduce the total ugliness.

样例 4

4 2
1 3 2 4
2 3
9