题解：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

数组时记录下当前的有效人数，以减少转移开销。

CPP

#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;
}

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

文章操作

相关推荐

评论

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