#P5869. [Usaco2024 Feb]Minimum Sum of Maximums P

    ID: 4899 传统题 1000ms 256MiB 尝试: 9 已通过: 4 难度: 9 上传者: 标签>CF2800省选/NOI-区间 DP状压 DP子掩码递推 (s-1)&mask交换论证添加哨兵

[Usaco2024 Feb]Minimum Sum of Maximums P

题目描述

贝西有 NN 块瓷砖排成一行,其中 2≤N≤3002\le N\le300。第 ii 块瓷砖的丑陋值为 aia_i,满足 1≤ai≤1061\le a_i\le10^6。

其中 KK 块瓷砖被固定在了位置上,0≤K≤min⁡(N,6)0\le K\le\min(N,6)。固定位置按递增顺序给出,满足 1≤x1<⋯<xK≤N1\le x_1<\cdots<x_K\le N。

贝西想要最小化所有瓷砖的总丑陋值,这个总丑陋值被定义为每对连续瓷砖中最大丑陋值的和,即 ∑i=1N−1max⁡(ai,ai+1)\sum_{i=1}^{N-1} \max \left(a_i, a_{i+1}\right) 。她可以进行任意次数的以下操作:选择两块没有被固定的瓷砖,并交换它们的位置。

我们需要确定,如果贝西以最优的方式进行操作,她能够达到的最小总丑陋值是多少。

输入格式

第一行包含 NN 和 KK 。

第二行包含瓷砖的丑陋值 a1,…,aNa_1, \ldots, a_N 。

第三行包含被固定的瓷砖的索引 x1,…,xKx_1,\ldots,x_K。K=0K=0 时没有索引。

输出格式

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

样例

3 0
1 100 10
110

贝西可以交换第二块和第三块瓷砖,使得 a=[1,10,100]a=[1,10,100] ,达到总丑陋值 max⁡(1,10)+\max (1,10)+ max⁡(10,100)=110\max (10,100)=110 。

另外,她也可以交换第一块和第二块瓷砖,使得 a=[100,1,10]a=[100,1,10] ,同样达到总丑陋值

max(100,1)+max(1,10)=110。max (100,1)+max (1,10)=110。
3 1
1 100 10
3
110

贝西可以交换第一块和第二块瓷砖,使得 a=[100,1,10]a=[100,1,10] ,达到总丑陋值 max⁡(100,1)+max⁡(1,10)=\max (100,1)+\max (1,10)= 110 。

3 1
1 100 10
2
200

瓷砖的初始总丑陋值是 max⁡(1,100)+max⁡(100,10)=200\max (1,100)+\max (100,10)=200 。 贝西只允许交换第一块和第三块瓷砖,这使得她无法降低总丑陋值。

4 2
1 3 2 4
2 3
9

数据范围

  • Input 5: K=0K=0
  • Inputs 6-7: K=1K=1
  • Inputs 8-12: N≤50N \leq 50
  • Inputs 13-24: No additional constraints