{"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 想要最小化瓷砖的总丑陋度，其中总丑陋度定义为每对相邻瓷砖的最大丑陋度之和；即 $\\sum\\limits^{N−1}_{i=1}\\max(a_i,a_{i+1})$。她可以任意次执行以下操作：选择两块均未卡住的瓷砖，并交换它们。\n\n求 Bessie 以最优方案执行操作可以达到的最小总丑陋度。 \n\n## Input\n\n输入的第一行包含 $N$ 和 $K$。\n\n第二行包含 $a_1,\\ldots,a_N$。\n\n第三行包含 $K$ 个索引 $x_1,\\ldots,x_K$。 \n\n## Output\n\n输出最小可能的总丑陋度。 \n\n[samples]\n\n## Note\n\n### 样例解释 1\n\nBessie 可以交换第二块和第三块瓷砖，使得 $a=[1,10,100]$，达到总丑陋度 $\\max(1,10)+\\max(10,100)=110$。或者，她也可以交换第一块和第二块瓷砖，使得 $a=[100,1,10]$，同样达到总丑陋度 $\\max(100,1)+\\max(1,10)=110$。\n\n### 样例解释 2\n\n瓷砖的初始总丑陋度为 $\\max(1,100)+\\max(100,10)=200$。Bessie 只允许交换第一块和第三块瓷砖，这并不能使她能够减少总丑陋度。\n\n### 测试点性质\n\n- 测试点 $5$：$K=0$。\n- 测试点 $6-7$：$K=1$。\n- 测试点 $8-12$：$N\\le 50$。\n- 测试点 $13-24$：没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10197","tags":["动态规划 DP","USACO","2024","O2优化","区间 DP"],"sample_group":[["3 0\n1 100 10","110"],["3 1\n1 100 10\n2","200"],["4 2\n1 3 2 4\n2 3","9"],["3 1\n1 100 10\n3","110"]],"created_at":"2026-03-03 11:09:25"}}