自动搬运

查看原文

来自洛谷，原作者为

	Bronya18C 人活着就是为了和美少女贴贴

搬运于2025-08-24 22:55:40，当前版本为作者最后更新于2024-02-23 15:42:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

赛时场切了，感觉相当有意思，来补一篇题解。

简要题意

给定一个长度为 $n$ 的序列，有 $K$ 个位置被固定住了，剩下的数之间可以随意交换，问最小的 $\sum_{i=1}^{n-1}\max(a_i,a_{i+1})$ 的权值是多少。

$n\le 300,K\le 6$。

分析性质

考虑将 $\max(a_i,a_{i+1})$ 拆成 $\dfrac{a_i+a_{i+1}+|a_i-a_{i+1}|}{2}$。

其中 $a_i+a_{i+1}$ 是固定的，意思就是我们要最小化 $|a_i-a_{i+1}|$ 的总和。

对于边界的情况，我们可以往两端塞入一个被固定的充分大的数 $C$，最后再减去这部分的答案即可。

由于原来固定的 $K$ 个位置将原序列分为至多 $K+1$ 段，考虑假如我们已经将数分配进了这 $K$ 段里面，段内如何分配才是最优。

由于段与段之间互不影响，我们考虑对于一段计算贡献。

考虑这一个段左边的数为 $L$，右边的数为 $R$，不失一般性地假设 $L\le R$。

那么我们肯定是将分配进来的数从左到右，从小到大排最优，因为可以通过如下的调整法证明：

1. 假如相邻的三个数 $x,y,z$ 满足 $x\ge y \le z$，那么将其变为 $y,x,z$ 不会更劣。

2. 同理，对于 $x\le y \ge z$ 将其变为 $x,z,y$ 不会更劣。

然后一直调整可以使分配的数有序，然后对于边界，我们已经假设 $L\le R$，那么把小的放左边肯定更优。

设这段数的最小值为 $mi$，最大值为 $ma$，那么这一段的贡献是 $|L-mi|+ma-mi+|R-ma|$。

则最后答案为

$$\sum_{i=1}^{K+1}|L_i-mi_i|+ma_i-mi_i+|R_i-ma_i|$$

答案只和每一段的最小值 $mi_i$ 和 $ma_i$ 有关。

考虑如何分配 $mi_i$ 和 $ma_i$。

性质：存在一种最优方案，使得对于任意的数对 $(i,j)$，都满足 $(mi_i,ma_i)$ 和 $(mi_j,ma_i)$ 的关系为相离或者包含。

证明：

还是考虑调整法，不妨设存在 $(i,j)$ 满足 $mi_i\lt mi_j \lt ma_i \lt ma_j$，则我们可以通过交换第 $i$ 段里最大的数和第 $j$ 段里最小的数，直到 $ma'_i\le mi'_j$，此时 $ma'_i \le ma_i$ 且 $mi'_j\ge mi_i$。

考虑 $ma_i$ 变小对第 $i$ 段贡献的影响，由于第 $i$ 段贡献与 $ma_i$ 有关的只有 $ma_i+|ma_i-R|$，分类讨论可得 $ma_i$ 变小后，这个式子要么不变要么变小。

同理 $mi_i$ 变大，对答案的贡献也要么不变要么变小。

所以这样调整会使得答案不劣。

证毕。

做法

从上面的式子我们可以得到一个大概的思路，通过确定每段的边界，然后将剩下的数填进去。

容易发现我们不关系中间的数怎么填的，只需要有一个合法的填数方案即可。

考虑我们从小到大考虑每个数，要么它作为某一段的左边界，要么它填入目前左边界最大的没填满的段（因为根据上面性质可知，左边界最大肯定有边界最小，我们先贪心地满足更紧的限制），此时若将这个段填满了就直接作为这个段右边界。

考虑我们如何实现这个填数过程，考虑区间 dp，设 $f_{l,r,S}$ 满足下标为 $[l,r]$ 的数已经填满集合为 $S$ 的段的最小贡献。

由上面的填数过程可知，我们不会在内部的小段留一些数给外面更大的段。（调整法也可以证明）

因此，设 $len_S$ 表示集合为 $S$ 的段的长度之和，满足 $f_{l,r,S}$ 最小且 $r-l+1$ 最小的 $l,r$ 一定满足 $r-l+1=len_S$。

于是我们只用考虑三种转移，

1. 目前左边/右边的数留给下一个包住它的段，$f_{l,r,S}=\min(f_{l+1,r,S},f_{l,r-1,S})$，这部分转移是 $O(1)$ 的，复杂度等于状态数 $O(2^Kn^2)$。

2. 把两端拼起来，考虑枚举子集，$f_{l,r,S}$ 可以从 $f_{l,l+len_{S'}-1,S'}+f_{r-len_{S-S'}+1,r,S-S'}$ 转移过来，复杂度为 $O(3^{K}n^2)$。

3. 用一个大段包住中间的小段，$f_{l,r,S}$ 可以从 $f_{l+1,r-1,S-\{x\}}+F_x(a_l,a_r)$，其中 $F_x(a_l,a_r)$，表示第 $x$ 段最小值为 $a_l$ 最大值为 $a_r$ 的贡献，这部分由于用大段包住小段的时候一定满足 $r-l+1=len_S$，所以复杂度为 $O(n2^{K}K)$ 的。

最后复杂度为 $O(3^Kn^2)$，瓶颈为第二种转移。

代码

#include<bits/stdc++.h>

using namespace std;
int n,k;
int a[305];
int b[305];
int ned[305];
int f[305][305][128];
int sum[128];
int L[305],R[305];
bool pd[305];
vector<int>sb;
int main(){
    scanf("%d%d",&n,&k);
    int ans=0;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),ans+=2*a[i];
    a[0]=1e6;a[n+1]=1e6;ans+=2e6;
    for(int i=2;i<=k+1;i++)scanf("%d",&b[i]),pd[b[i]]=true;
    b[1]=0;b[k+2]=n+1;
    for(int i=1;i<=n;i++)
        if(!pd[i])sb.push_back(a[i]);
    int K=0;
    for(int i=1;i<=k+1;i++){
        if(b[i]==b[i+1]-1){ans+=abs(a[b[i+1]]-a[b[i]]);continue;}
        ned[++K]=b[i+1]-b[i]-1;L[K]=a[b[i]];R[K]=a[b[i+1]];
        if(L[K]>R[K])swap(L[K],R[K]);
    }sb.push_back(-1);
    sort(sb.begin(),sb.end());
    int m=sb.size()-1;
    for(int j=0;j<(1<<K);j++)
        for(int i=1;i<=K;i++)
            if(j&(1<<i-1))sum[j]+=ned[i];
    for(int l=0;l<=m+1;l++)
        for(int r=0;r<=m+1;r++)
            for(int j=0;j<(1<<K);j++)
                f[l][r][j]=(j==0?0:1e9);
    for(int i=1;i<=m;i++){
        for(int l=1;l+i-1<=m;l++){
            int r=l+i-1;
            for(int j=0;j<(1<<K);j++){
                f[l][r][j]=min(f[l+1][r][j],f[l][r-1][j]);
                if(sum[j]>i)continue;
                if(sum[j]==i){
                    for(int x=1;x<=K;x++)
                        if(j&(1<<x-1)){
                            if(ned[x]==1&&i==1)f[l][r][j]=min(f[l][r][j],abs(L[x]-sb[l])+abs(R[x]-sb[l]));
                            else if(ned[x]>1)
                                f[l][r][j]=min(f[l][r][j],f[l+1][r-1][j^(1<<x-1)]+abs(L[x]-sb[l])+abs(R[x]-sb[r])+sb[r]-sb[l]);
                        }
                }
                for(int s=(j-1)&j;s;s=(s-1)&j)
                    f[l][r][j]=min(f[l][r][j],f[l][l+sum[s]-1][s]+f[l+sum[s]][r][j^s]);
                // cerr<<l<<" "<<r<<" "<< j<<" "<<f[l][r][j]<<endl;
            }
        }
    }
    ans+=f[1][m][(1<<K)-1];//cerr<<f[1][m][(1<<K)-1]<<endl;
    ans/=2;ans-=2e6;
    printf("%d\n",ans);
    return 0;
}