题解：P10156 [LSOT-2] 胜者组

· · 题解

有一道题和本题非常像，可以说是本题的弱化版，建议先去看看：P4158 粉刷匠。

对于本题，我们发现可以类比上面那道题的套路，先对于每个小团体内部 dp 求一遍答案，再对所有小团体跑分组背包把答案整合起来。（第三个部分分或许对此有所启发）

现在的问题就是如何算每个小团体内部的贡献，发现很烦人的一点是看起来小团体内部的组合方式是不确定的。再观察算贡献的式子 a_i+a_j+x\times|i-j| 发现 a_i+a_j 是无论如何都要选的，变数就在于后半部分的绝对值。

如果做题够多，又看到贡献里有下标距离（即下标的差的绝对值），应该第一反应就是借助贪心排序。

考虑假设我们已经选定了某个小团体中要留下的下标集合 S，那接下来的任务就是给集合中的元素两两配对，形成含有若干二元组的集合 P，我们要通过合理地顺序安排使得 \sum_{(i,j)\in P} x\cdot|i-j| 最小。

应该不难想到最优策略应该满足：如果把 P 中每个二元组看成一条线段，则集合内任意线段两两不重叠。因为如果对于两个二元组 (a,b),(c,d) \in P，满足 a \le c \le d \le b，那么组合成 (a,c),(b,d) 显然会更优（距离之和显然更小）。

由此，我们可以得出：选择的所有人一定两两相邻，不会出现隔着人跳跃选择的情况，这样就能 dp 了。

先设 f_{i,j,0/1} 表示小团体中前 i 个人中，留下 j 个学信息学，之前剩余一个未匹配/全部配对时的最小不满度。把贡献拆成 a_i-ix+a_j+jx，不难得出转移：f_{i,j,0}=\min\{f_{i-1,j-1,0}, f_{i-1,j,1}+a_i+x\times i\}，f_{i,j,1}=\min\{f_{i-1,j-1,1}, f_{i-1,j,0}+a_i-x\times i\}。（考虑留/不留第 i 个人）

然后设 g_{i,j} 表示前 i 个小团体留下 j 个人的最小不满值，用分组背包合并每一行答案即可。

因为所有小团体加起来总共有 n 个人，所以时间复杂度是 O(n^2) 级别的。可以考虑在合并 g 数组时记录下当前的有效人数，以减少转移开销。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5005;
const ll inf = 1e18;

int n, m, p, x, a[maxn];
vector<int> t[maxn];

void solve()
{
    cin >> n >> m >> p >> x;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    for(int c, i = 1; i <= n; i ++){
        cin >> c; t[c].push_back(i);
    }
    vector<vector<ll>> g(n + 1, vector<ll>(m + 1, inf));
    g[0][0] = 0;
    int s = 0; // 记录当前的有效人数
    for(int i = 1; i <= p; i ++){
        vector<vector<array<ll, 2>>> f(t[i].size() + 1, vector<array<ll, 2>>(m + 1, {inf, inf})); // 注意开的大小有说法，开大了TLE
        f[0][0][0] = 0;
        for(int j = 1; j <= t[i].size(); j ++){ // 注意这里j从1开始枚举，但t[i]下标是从0开始的
            for(int k = 0; k <= m; k ++){
                f[j][k][0] = min(f[j-1][k][1]+a[t[i][j-1]]+1LL*x*t[i][j-1], k>0?f[j-1][k-1][0]:inf); // 避免k-1越界
                f[j][k][1] = min(f[j-1][k][0]+a[t[i][j-1]]-1LL*x*t[i][j-1], k>0?f[j-1][k-1][1]:inf);
            }
        }
        s += t[i].size();
        for(int j = 0; j <= s; j ++){
            for(int k = 0; j + k <= m && k <= t[i].size(); k ++){ // 注意j+k不要越界
                g[i][j+k] = min(g[i][j+k], g[i-1][j]+f[t[i].size()][k][0]);
            }
        }
    }
    ll ans = inf;
    for(int j = 0; j <= m; j ++){ // 枚举所有可能留下的人数
        ans = min(ans, g[p][j]);
    }
    if(ans >= 1e15) cout << "Impossible\n";
    else cout << ans << '\n';
}

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