考虑两个固定的数中间放了一堆数，我们的最优策略是什么。

打个表可以发现是排序一下，然后固定的数大的放在排序的较大一侧。

尝试证明这个结论：从小到大放数，每次放数的时候考虑其增加的 $\sum\max(a_i,a_{i+1})$ 的最小值，显然在这一种排序方式下都能取到。

在证明这个结论之后，我们发现，被夹在中间的数对答案的贡献都是 $1$。所以，我们不妨将答案减掉所有数，然后再考虑贡献。

所以假设我们选了一些数，我们只关心我们选的最小值和最大值。考虑两边的数分别是 $a,d$，且有 $a< d$，最小值和最大值分别是 $b,c$，贡献即为 $\max(a,b)-b+\max(c,d)$。

唔…这意味着什么？答案是最小值最大值独立了，我们只需要选 $2k$ 个点。

但是选 $2k$ 个点对中间的点的个数仍然有限制，暴力做大概只能做到 $O((\frac{n}{k+1})^{k+1})$。

还能优化吗？答案当然是可以的。关于 $b$ 的部分 $a$ 不变 $b$ 越大越优，关于 $c$ 的部分 $d$ 不变 $c$ 越小越优，所以当两个点对满足相对关系是 $L_1,L_2,R_1,R_2$ 的时候显然存在更优的交换。

这下似乎很可以做了！区间端点要么包含要么相交，考虑区间 DP，状态为 $f_{l,r,S}$ 代表已经决策完了 $[l,r]$ 这段区间，已经拿完了集合 $S$ 的最小代价。

直接做时间复杂度可以高达 $O(n^33^k)$，但是进行一些有效状态剪枝可以在时限内通过。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
bool vis[303];
int arr[303],a[303],pos[13];
int sz[13],mx[13],lv[13],rv[13];
int sum,n=read(),m=read(),L;
int calc(int l,int r,int x)
{return max(a[l],lv[x])-a[l]+max(a[r],rv[x]);}
int f[303][303][128];
signed main()
{
    pos[m+1]=n+1,arr[0]=arr[n+1]=5e7;
    for(int i=1; i<=n; ++i) arr[i]=read();
    for(int i=1; i<=m; ++i) vis[pos[i]=read()]=1;
    for(int i=0; i<=m; ++i)
    {
        lv[i]=arr[pos[i]],rv[i]=arr[pos[i+1]];
        mx[i]=sz[i]=pos[i+1]-pos[i]-1;
        if(lv[i]>rv[i]) swap(lv[i],rv[i]);
    }
    int sum=0,M=1<<(m+1),req=0;
    for(int i=1; i<=n; ++i) if(!vis[i]) sum+=(a[++L]=arr[i]);
    for(int i=0; i<=m; ++i)
    if(!sz[i]) sum+=max(lv[i],rv[i]);
    else req+=(1<<i);
    sort(a+1,a+L+1);
    memset(f,0x3f,sizeof(f));
    for(int len=1; len<=L; ++len)
        for(int l=1,r=len; r<=L; ++l,++r)
        {
            for(int i=0; i<=m; ++i) if(sz[i]==len)    
            {
                f[l][r][1<<i]=calc(l,r,i);
            }
            else if(sz[i]>0&&sz[i]<len)
            {
                int A=calc(l,r,i);
                for(int L=l,R=r-sz[i]; R<=r; ++L,++R)
                    for(int q=0; q<M; ++q) if((q>>i)&1)
                        f[l][r][q]=min(f[l][r][q],
                        f[L][R][q-(1<<i)]+A);
            }
            for(int d=l; d<r; ++d)
            {
                for(int k=0; k<M; ++k) if(f[l][d][k]<1e9)
                {
                    int o=M-1-k;
                    do{
                    if(((k&o)==0)&&f[d+1][r][o]<1e9)
                    f[l][r][k+o]=min(f[l][r][k+o],
                    f[l][d][k]+f[d+1][r][o]);
                    o=(o-1)&(M-1-k);
                    }while(o!=M-1-k);
                }
            }
        }
    if(L==0) printf("%d\n",sum-arr[0]-arr[n+1]);
    else printf("%d\n",f[1][L][req]-arr[0]-arr[n+1]+sum);
    return 0;
}