自动搬运

查看原文

来自洛谷，原作者为

	ylch 博观而约取，厚积而薄发 加油！（查看.com域名帖子中的内容，把后缀改成.me即可）

搬运于2025-08-24 22:48:38，当前版本为作者最后更新于2025-07-22 23:35:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

有一个很妙的思路，分享一下。

根据题目的意图，我们要在移动距离最短前提下，使得数组的前 $F$ 个元素的和大于等于 $T$。显然只能从后往前移动，不然无意义。

设选中的 $F$ 个元素在原数组中的位置为 $x_1 \leq x_2 \leq \dots \leq x_F$，经过交换后在前 $F$ 个位置的最终位置为 $y_1 < y_2 < \dots < y_F$（其中 $y_i \in [1,F]$）。

将元素从 $x_i$ 移动到 $y_i$ 需要 $|x_i - y_i|$ 次相邻交换，总交换次数即为 $\sum\limits_{i=1}^F (x_i - y_i)$，因为 $x_i \geq y_i$。

显然不管怎么交换，原来位置和 $\sum x_i$ 一定等于交换后的位置和 $\sum y_i$ 加上交换时移动的距离（就是交换次数）。

设交换次数为 $t$，则 $\sum x_i = \sum y_i + t$，移项可得 $t = \sum x_i - \sum y_i$。

可得对于前 $F$ 个位置，$y_i$ 固定取 $1,2,3,\dots F$，位置和等于 $\frac{F(F+1)}{2}$。

所以，最小交换次数的计算方法如下：

$$t=\sum x_i - \frac{F(F+1)}{2}$$

要使得交换次数 $t$ 最小，就要使得 $\sum x_i$ 尽可能小。

---

所以，我们要选中 $F$ 个数值总和大于等于 $T$ 的数，在数值总和都大于等于 $T$ 时就让位置和最小。

不难想到这一步可以用 dp 解决。设 $dp_{i,j,k}$ 表示当前在位置 $i$，选了 $j$ 个元素，选中的所有元素下标和为 $k$ 时的最大数值总和。

转移方程比较简单，只要对于每个不同的元素 $i$，尝试加入之前不同的状态就行了：

$$dp_{i,j,k} = \max\{ dp_{i-1,j-1,k-i} + a_i \}\ (j \le \min\{i,F\}) $$

转移时可以滚动数组，不过要倒序枚举 $j$。

时间复杂度约为 $O(5000 \times nF)$（$\frac{100(100+1)}{2}=5050$）。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll N, F, T;
ll a[105], dp[105][5100]; // dp[j][k]:（当前第i个数）选了j个，下标和为k时，数值和的最大值

void solve()
{
    cin >> N >> F >> T;
    for(int i = 1; i <= N; i ++){
        cin >> a[i];
    }

    memset(dp, -0x3f, sizeof dp);
    dp[0][0] = 0;
    for(int i = 1; i <= N; i ++){
        for(int j = min(1LL*i, F); j >= 1; j --){
            for(int k = i; k <= 5050; k ++){ // 100*(100+1)/2 = 5050
                dp[j][k] = max(dp[j][k], dp[j - 1][k - i] + a[i]);
            }
        }
    }

    int minp = 1e9;
    for(int k = 0; k <= 5050; k ++){
        if(dp[F][k] >= T) minp = min(minp, k);
    }
    if(minp == 1e9) puts("NO"); else cout << max(0LL, 1LL*minp - F*(F+1)/2) << '\n';
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
    return 0;
}