[USACO24FEB] Minimum Sum of Maximums P

Luogu

IDLGP10197

Time2000ms

Memory256MB

DifficultyP7

动态规划 DPUSACO2024O2优化区间 DP

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 以最优方案执行操作可以达到的最小总丑陋度。 ## Input 输入的第一行包含 $N$ 和 $K$。第二行包含 $a_1,\ldots,a_N$。第三行包含 $K$ 个索引 $x_1,\ldots,x_K$。 ## Output 输出最小可能的总丑陋度。 [samples] ## Note ### 样例解释 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$：没有额外限制。

Samples

Input #1

3 0
1 100 10

Output #1

Input #2

3 1
1 100 10
2

Output #2

Input #3

4 2
1 3 2 4
2 3

Output #3

Input #4

3 1
1 100 10
3

Output #4

API Response (JSON)

{
  "problem": {
    "name": "[USACO24FEB] Minimum Sum of Maximums P",
    "description": {
      "content": "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 想要最小化瓷砖的总丑陋",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10197"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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$）的瓷砖。\n\nBessie 想要最小化瓷砖的总丑陋...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments