Problem Link

题目大意

给定长度为 $n$ 的序列 $a_1\sim a_n$，给定 $k$ 个位置不能交换，其他位置上的元素可以任意交换，最小化 $\sum\limits_{i=1}^{n-1}\max(a_i,a_{i+1})$。

数据范围：$n\le 300,k\le 6$。

思路分析

从 $k=0$ 的情况开始，注意到 $\max(a_i,a_{i+1})=\dfrac 12(a_i+a_{i+1}+|a_i-a_{i+1}|)$，因此我们只要最小化 $\sum |a_i-a_{i+1}|$，升序或降序排列即可。

回到一般的问题，我们设 $a_0=a_{n+1}=\infty$ 且这两个位置不能交换，那么整个序列就被不能交换的点分成若干个区间 $(l_i,r_i)$，我们只要把可以交换的元素填入这些区间即可。

假设我们在区间 $(l_i,r_i)$ 中填的元素是 $S$，根据刚才的结论，显然 $S$ 升序排列或降序排列最优，如果 $a_{l_i}<a_{r_i}$ 那么升序排列，否则降序排列。

设 $S$ 中元素的最大最小值分别为 $\max_i,\min_i$，那么这一段区间的贡献就是 $|a_{l_i}-\min_i|+|a_{r_i}-\max_i|+\max_i-\min_i$。

注意到关于 $\max_i$ 的贡献为 $|a_{r_i}-\max_i|+\max_i$ 随着 $\max_i$ 变小递减，关于 $\min_i$ 的贡献 $|a_{l_i}-\min_i|-\min_i$ 随着 $\min_i$ 变大递减。

因此可以通过调整法证明每个区间内的值域区间 $[\min_i,\max_i]$ 要么相离要么包含，否则可以把相交区间切成两部分，使得 $\max_i$ 变小 $\min_j$ 变大。

那么就可以考虑在值域上 dp，设可以交换的元素排序后是 $w_1\sim w_m$，那么设 $f_{l,r,S}$ 表示考虑 $S$ 中的区间用 $w_l\sim w_r$ 中的元素填满的最小代价。

根据代价函数的性质进一步分析，我们发现：对于两个值域区间 $[\min_i,\max_i]\subseteq[\min_j,\max_j]$，$[\min_i,\max_i]$ 内部不可能有元素在 $j$ 中，否则交换该元素和 $\min_i$ 即可让 $\min_i$ 变大。

设 $S$ 中的区间大小总和为 $siz_S$，那么我们只要在 $r-l+1=siz_S$ 时考虑向 $S$ 中插入一个区间，否则直接从 $\min(f_{l,r-1,S},f_{l+1,r,S})$。

考虑插入区间的形式：

• 合并两个值域区间，枚举 $T\subset S$ 后从 $f(l,l+siz_T-1,T)+f(l+siz_T,r,S\setminus T)$ 转移。
• 插入一个区间 $x$：
  • 特判 $x$ 大小为 $1$ 的情况，可以钦定这种情况最先考虑，只需要在 $l=r$ 时计算，通过合并操作即可转移。
  • 否则一定插入 $\min_x=w_l,\max_x=w_r$ 的若干个元素，算出其转移代价后从 $f(l+1,r-1,S\setminus\{x\})$ 转移。

时间复杂度 $\mathcal O(n^2(3^k+k2^k))$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int V=1e6+5;
int a[305],L[10],R[10],len[10],sz[1<<7],w[305],id[10],f[305][305][1<<7];
void chkmin(int &x,int y) { x=x<y?x:y; }
signed main() {
	int N,M,n=0,m=0,ans=0;
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;++i) scanf("%d",&a[i]),ans+=2*a[i];
	for(int i=1;i<=M;++i) scanf("%d",&id[i]);
	a[0]=a[N+1]=V,id[0]=0,id[M+1]=N+1,ans+=2*V;
	for(int i=0;i<=M;++i) {
		if(id[i+1]-id[i]==1) ans+=abs(a[id[i]]-a[id[i+1]]);
		else {
			L[m]=id[i],R[m]=id[i+1],len[m]=R[m]-L[m]-1;
			for(int j=L[m]+1;j<=R[m]-1;++j) w[++n]=a[j];
			if(a[L[m]]>a[R[m]]) swap(L[m],R[m]); ++m;
		}
	}
	sort(w+1,w+n+1);
	for(int s=0;s<(1<<m);++s) for(int i=0;i<m;++i) if(s>>i&1) sz[s]+=len[i];
	memset(f,0x3f,sizeof(f));
	for(int i=0;i<=n;++i) f[i+1][i][0]=0;
	for(int d=1;d<=n;++d) for(int l=1,r=d;r<=n;++l,++r) for(int s=0;s<(1<<m);++s) if(sz[s]<=d) {
		f[l][r][s]=min(f[l][r-1][s],f[l+1][r][s]);
		for(int t=(s-1)&s;t;t=(t-1)&s) {
			chkmin(f[l][r][s],f[l][l+sz[t]-1][t]+f[l+sz[t]][r][s^t]);
		}
		if(sz[s]<d) continue;
		for(int j=0;j<m;++j) if(s>>j&1) {
			int z=abs(a[L[j]]-w[l])+abs(a[R[j]]-w[r])+w[r]-w[l];
			if(len[j]==1&&d==1) {
				chkmin(f[l][r][s],z);
			} else if(len[j]>1) {
				chkmin(f[l][r][s],f[l+1][r-1][s^(1<<j)]+z);
			}
		}
	}
	printf("%d\n",(ans+f[1][n][(1<<m)-1])/2-2*V);
	return 0;
}