Holding

思路

根据思考。将 (i,j) 直接交换，相当于 i 到 j 一直邻项交换。

如果交换的路径呈现包含，那么不如交换一下各自交换的的对象，使得 k 更小。

为什么呢？会使得 k 更小呢？因为我们是邻项交换的，所以无论范围大的那对是先还是后，都会使得范围小的那对向左移动一格，那么就需要 +2 步来挪回原位。

其实就算不是邻项交换，那么交换了也不会使得答案更差。

所以，假设我们现在选择了 k 个数放进区间 [l,r]。那么在区间 [l,r] 的顺序的顺序和他们原本在序列中的序列相同。

设计 DP 为 f_{i,j,k} 表示到第 i 个数为止，一共选择了 j 个数进入 [l,r]，并且花费了 k 步时区间 [l,r] 的最小价值。

考虑转移。

• 首先可以不选 i。那么 f_{i,j,k}=f_{i-1,j,k}。
• 否则可以选 i，那么此时 f_{i,j,k}=\min(f_{i,j,k},f_{i-1,j-1,k-dis(i,l+j-1)}+a_{i})。

时间复杂度 O(n^{2}\times k)。利用滚动数组，空间可以优化为 O(n\times k)。

代码

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N=110;
const int K=1e4+10;
const int INF=0x3f3f3f3f;

typedef long long ll;
typedef pair<int,int> pii;

int n,l,r,maxf;
int a[N];
int f[2][N][K];

int main(){
    freopen("holding.in","r",stdin);
    freopen("holding.out","w",stdout);

    ios::sync_with_stdio(0);

    memset(f,INF,sizeof f);
    f[0][0][0]=0;

    cin>>n>>l>>r>>maxf;

    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++){
        for(int j=0;j<=r-l+1;j++){
            for(int k=0;k<=maxf;k++){
                int w=abs(l+j-i-1);//移动距离 
                f[i&1][j][k]=f[(i-1)&1][j][k];
                if(k>=w&&j>=1) f[i&1][j][k]=min(f[i&1][j][k],f[(i-1)&1][j-1][k-w]+a[i]);
            }
        }   
    }

    int ans=1e9;

    for(int k=0;k<=maxf;k++){
        ans=min(ans,f[n&1][r-l+1][k]);
    }

    cout<<ans<<endl;

    return 0;
}//end