比赛链接

给定长度为 $n$ 的序列，交换任意两个相邻元素的费用为 $1$。

每个元素的取值范围为 $[1\sim k]$，问使得序列的一个连续子序列恰好为 $1,2\cdots k$ 的最小费用。

首先假设固定所选元素的初始下标为 $p_1\lt p_2\lt \cdots \lt p_k$，且最终这 $k$ 个元素的下标 $[x,x+k-1]$。

不妨记权值等于 $i$ 的元素的位置为 $b_i$，同时设 $c_i=x+i-1$。

先证明该情况下的最小费用为 $\sum_{i=1}^k |p_i-c_i|+\text{inv}(b_1,b_2\cdots,b_k)$。其中 $\text{inv}B$ 表示序列 $B$ 中的逆序对。

首先证明答案的下界为 $\sum_{i=1}^k |p_i-c_i|+\text{inv}(b_1,b_2\cdots,b_k)$。

定义 $f(P)=\sum_{i=1}^k |p_i-c_i|+\text{inv}(b_1,b_2\cdots,b_k)$ 为序列 $P$ 的势能(一定要保证 $p_1\lt p_2\lt \cdots \lt p_k$)。

如果某次交换的两个元素都属于所选元素，则 $P$ 不变，$\text{inv}B$ 至多减少 $1$。

如果某次交换的至多有一个元素都属于所选元素，则 $\sum_{i=1}^k |p_i-c_i|$ 至多减 $1$，$\text{inv}B$ 不变。

接下来构造可以取到下界的方案，其实只要先在不交换相对位置的情况下将所有元素移到 $[x,x+k-1]$ 然后再调整次序消除逆序对即可。

接下来考虑固定所选元素的初始下标为 $p_1\lt p_2\lt \cdots \lt p_k$，如何确认最优的最终下标 $[x,x+k-1]$。

由于此时 $\text{inv}(b_1,b_2\cdots,b_k)$ 是定值，所以只需要考虑 $\sum_{i=1}^k |p_i-c_i|$。记 $m=\lceil \frac k2\rceil$，不难发现 $x_m=c_m$ 时最优。此时有

$$ \sum_{i=1}^k |p_i-c_i|=\sum_{i=1}^m (c_i-p_i)+\sum_{i=m+1}^k (p_i-c_i)=\sum_{i=1}^m (p_m-p_i-(m-i))+\sum_{i=m+1}^k (p_i-p_m-(i-m)) $$

上式中 $i\lt m$ 的 $p_i$ 系数为 $1$，$i\gt m$ 的 $p_i$ 系数为 $-1$，而 $p_m$ 系数根据 $k$ 的奇偶性为 $0$ 或 $-1$。

其他项是关于 $m$ 的多项式，为定值。因此在 $\text{dp}$ 过程中维护上式式子的结果和逆序对即可。时间复杂度 $O\left(n2^k\right)$。

const int MAXN=205,MAXK=17,inf=1e9;
int a[MAXN],dp[1<<MAXK],bt[MAXK][1<<MAXK];
int main()
{
	int n=read_int(),k=read_int(),s=1<<k;
	for(int i=k-1;i>=0;i--){
		_for(j,0,s){
			if(j&(1<<i))
			bt[i][j]=bt[i+1][j]+1;
			else
			bt[i][j]=bt[i+1][j];
		}
	}
	int m=(k+1)/2,a;
	_for(i,0,s)dp[i]=inf;
	dp[0]=0;
	_for(i,0,n){
		a=read_int()-1;
		_for(j,0,s){
			if(!(j&(1<<a))){
				int v=dp[j]+bt[a][j];
				if(bt[0][j]>=m)
				v+=i;
				else if(bt[0][j]+1==m){
					if(k%2==0)
					v-=i;
				}
				else
				v-=i;
				dp[j|(1<<a)]=min(dp[j|(1<<a)],v);
			}
		}
	}
	int ans=dp[s-1];
	_rep(i,1,k)
	ans-=abs(m-i);
	enter(ans);
	return 0;
}