题解：P9468 [EGOI 2023] Candy / 糖果

· · 题解

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

根据题目的意图，我们要在移动距离最短前提下，使得数组的前 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;
}