USACO 24 Feb Pt T2 题解
Bronya18C
·
·
题解
赛时场切了，感觉相当有意思，来补一篇题解。
简要题意
给定一个长度为 n 的序列，有 K 个位置被固定住了，剩下的数之间可以随意交换，问最小的 \sum_{i=1}^{n-1}\max(a_i,a_{i+1}) 的权值是多少。
## 分析性质
考虑将 $\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)$，瓶颈为第二种转移。
## 代码
```cpp
#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;
}
```