考虑dp，dp[i][j][k]为前 i 个数字，取前 j 个数字的最小和，交换 k 次的最小值。
然后可以从前面 j-1 的位置转移而来。
AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> #define int long long using namespace std; const int N=155; int n,k,s,a[N],dp[2][N][N*N],now; signed main(){ cin>>n>>k>>s; for(int i=1;i<=n;i++) cin>>a[i]; memset(dp,0x3f,sizeof dp); dp[0][0][0]=0; for(int i=1;i<=n;i++){ now^=1; memset(dp[now][0],0,sizeof dp[now][0]); for(int j=1;j<=i;j++){ for(int k=0;k<=i*j;k++){ dp[now][j][k]=dp[now^1][j][k]; if(k>=i-j) dp[now][j][k]=min(dp[now][j][k],dp[now^1][j-1][k-(i-j)]+a[i]); } } } int res=1e18; for(int i=0;i<=min(n*(n-1)/2,s);i++) res=min(res,dp[now][k][i]); cout<<res; return 0; }