Kevin 原创：

这道题大概 $5$ 分钟就想出来了，但是很难写也调了很久。

首先我们会发现交换无疑是和原区间左右两边的区间交换。

我们很快就会得出一个结论：存在 $p \in [L,R]$，使得对于任意 $x \in [L,p)$，点 $x$ 只会和原区间左边的点交换；对于任意 $x \in (p,R]$，点 $x$ 只会和原区间右边的点交换，至于 $p$ 就随意了。

容易证明，这个结论是成立的。具体的我就不再赘述了。

好了，我们现在就可以设两个装态 $l$ 和 $r$ 分别表示 $p$ 以前交换和 $p$ 以后交换的最大收益了，最后背包合并即可。

但是这个状态怎么设定呢？

很容易想到 $l[i][j]$ 为目前 $[L,i]$ 的所有文件都已经交换或留存了，共花了 $j$ 库纳的最大收益。（收益为原区间权值之和减去交换后的权值之和）

但是有一个问题，就是一个地方最多被交换一次，这个状态很容易重复。

这个就有一点思维含量了。所以我又推了一会，发现：对于任意 $1 \le a_1 < a_2 < L$ 和 $L \le b_1 < b_2 \le R$，交换 $a_1,b_2$ 和 $a_2,b_1$ 本质上与交换 $a_1,b_1$ 和 $a_2,b_2$ 的代价和收益其实是一样的。

这样就得到一个新的状态：$l[i][j][k]$ 为目前 $[L,i]$ 的所有文件都已经交换或留存了，且 $[1,L)$ 中被交换过的下标中最大为 $j$，共花了 $k$ 库纳的最大收益。（收益为原区间权值之和减去交换后的权值之和）

然后给第一维滚动数组优化，加一个 $s1,s2$ 记录最大数值最后背包合并即可。

时间复杂度 $O(N^2K)$，空间复杂度 $O(NK)$。代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=110,M=1e4+10;
int L[2][N][M],R[2][N][M],a[N],s1[N][M],s2[N][M];
signed main()
{
	int n,l,r,kk;cin>>n>>l>>r>>kk;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=l;i<=r;i++)
	{
		for(int j=0;j<=kk;j++)
			for(int al=0;al<l;al++)for(int ar=al+1;ar<l;ar++)if(j+(i-ar)<=kk)
				L[1][ar][j+(i-ar)]=max(L[1][ar][j+(i-ar)],L[0][al][j]+(a[i]-a[ar]));
		for(int j=0;j<=kk;j++)for(int k=0;k<l;k++)L[0][k][j]=L[1][k][j];
		for(int j=0;j<=kk;j++)s1[i][j]=s1[i-1][j];
		for(int j=0;j<=kk;j++)for(int k=0;k<l;k++)s1[i][j]=max(s1[i][j],L[0][k][j]);
	}
	for(int i=r;i>=l;i--)
	{
		for(int j=0;j<=kk;j++)
			for(int al=n+1;al>r;al--)for(int ar=al-1;ar>r;ar--)if(j+(ar-i)<=kk)
				R[1][ar][j+(ar-i)]=max(R[1][ar][j+(ar-i)],R[0][al][j]+(a[i]-a[ar]));
		for(int j=0;j<=kk;j++)for(int k =n+1;k>r;k--)R[0][k][j]=R[1][k][j];
		for(int j=0;j<=kk;j++)s2[i][j]=s2[i+1][j];
		for(int j=0;j<=kk;j++)for(int k=n+1;k>r;k--)s2[i][j]=max(s2[i][j],R[0][k][j]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=kk;j++)
			s1[i][j]=max(s1[i][j],s1[i][j-1]),
			s2[i][j]=max(s2[i][j],s2[i][j-1]);
	}
	int ans=0;
	for(int i=l-1;i<=r;i++)
		for(int j=0;j<=kk;j++)
			ans=max(ans,s1[i][j]+s2[i+1][kk-j]);
	int sum=0;for(int i=l;i<=r;i++)sum+=a[i];sum-=ans;
	cout<<sum;
	return 0;
}

但是别忘了这玩意是有状态继承的，我就忘了结果把滚动数组清零了调了很久。

题解

容易发现交换 $i,j$ 两个元素并花费 $|i-j|$ 元，相当于进行了 $|i-j|$ 次邻项交换。因此原命题等价于进行不超过 $k$ 次邻项交换使得 $[l, r]$ 区间内的元素之和最小。

我们考虑在最终序列里，有哪些元素被选择进 $[l, r]$。将这些元素在原数列中的下标按照从小到大排列记为 $p_1,p_2,\cdots,p_m$，那么在最优决策下，$p_1$ 移动到了 $l$，$p_2$ 移动到了 $l+1$，……，$p_i$ 移动到了 $l+i-1$。为什么？假定移动两个元素 $i,j$ 时，路径发生了交叉，那么必然发生了交换 $i,j$ 两个元素的情形，这一定会更劣。

那么 $\mathrm{dp}$ 设计就非常简单。设前 $i$ 个数，选择了 $j$ 个，花费了恰好 $t$ 元的情况下，选出的元素的最小值为 $f_{i,j,t}$，容易得到状态转移方程：

$$f_{i,j,t}=\min\{f_{i-1,j,t},f_{i-1,j-1,t-|l+j-i-1|}+a_i\}$$

直接暴力转移，时间复杂度为 $\mathcal O(n^2k)$。使用滚动数组优化空间，空间复杂度为 $\mathcal O(nk)$。

参考代码

#include<bits/stdc++.h>
#define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 1e9 + 1;
const int MAXN= 100 + 3;
const int MAXM= 1e4 + 3;
int F[2][MAXN][MAXM], o, n, m, l, r, t, A[MAXN];
int qread(){
    int w = 1, c, ret;
    while((c = getchar()) >  '9' || c <  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
    return ret * w;
}
int main(){
    n = qread(), l = qread(), r = qread(), m = qread();
    t = r - l + 1;
    up(1, n, i) A[i] = qread();
    up(0, t, i) up(0, m, j)
        F[0][i][j] = F[1][i][j] = INF;
    F[o][0][0] = 0;
    up(1, n, i) {
        up(0, t, j) up(0, m, k){
            int w = abs(l + j - i - 1);
            F[!o][j][k] = F[o][j][k];
            if(k >= w && j >= 1)
                F[!o][j][k] = min(F[!o][j][k], F[o][j - 1][k - w] + A[i]);
        }
        o ^= 1;
    }
    int ans = INF;
    up(0, m, i) ans = min(ans, F[o][t][i]);
    printf("%d\n", ans);
    return 0;
}