题意简述

有 $n$ 件物品，每件物品有一种颜色和一个价值。需要从 $k$ 种颜色中各选一件物品，最大化所选价值两两差的绝对值之和。

思路

先把每种颜色的物品压缩成一个区间。设这类物品的最小、最大价值分别为 $L_i,R_i$。固定其他颜色所选的价值后，当前颜色选择 $x$ 的贡献为 $\sum_j|x-x_j|$，这是关于 $x$ 的凸函数，在 $[L_i,R_i]$ 上的最大值一定能在端点取得。依次对每种颜色这样处理，就能得到一个只选端点的最优解。两个端点都对应实际存在的物品，因此我们也可以暂时允许在每个区间内选任意实数，最优值仍然相同。

剩下的困难是：计算两个区间之间的贡献时，两边都还有左右端点的选择。我们希望把它拆成两部分，一部分只由较早处理的区间决定，另一部分只需要知道之前有多少个区间选了左端点、多少个选了右端点。记 $d_i=R_i-L_i$，将所有区间按 $d_i$ 从大到小排序，后文的编号均指排序后的编号。

对于 $i<t$，先规定一种新的计分方式：若 $i$ 选左端点，基础贡献为 $|L_i-L_t|$；若 $i$ 选右端点，基础贡献为 $|R_i-R_t|$。如果两者选择不同侧，再加上 $d_t$。选择同侧时，它就是真实距离；选择不同侧时，由三角不等式，有

$$ \begin{aligned} |L_i-R_t|&\le |L_i-L_t|+d_t,\\ |R_i-L_t|&\le |R_i-R_t|+d_t. \end{aligned} $$

把所有物品对的新贡献相加，称为这组左右选择的上界分数。这个分数可能严格大于该方案的真实得分，所以仅有三角不等式还不足以保证算法正确。接下来证明：任意一组左右选择的上界分数，都不超过原问题的最优值。 结合上界分数不小于真实得分，就能说明两种计分方式的最大值相等。

为此，把一组固定的左右选择看成点的运动。第 $i$ 个点在时刻 $-d_i$ 出现在区间中点，此后以速度 $1/2$ 向选定的端点移动，在时刻 $0$ 到达端点。对于 $i<t$，当点 $t$ 出现时，点 $i$ 与它的距离恰好是基础贡献：例如 $i$ 向左移动时，两点的位置分别为 $L_i+d_t/2$ 和 $L_t+d_t/2$，距离为 $|L_i-L_t|$。此后两点还会共同运动 $d_t$ 的时间。新计分方式把同向运动的距离增加量计为 $0$，把反向运动的距离增加量计为 $d_t$。因此，上界分数可以分成各次新点出现时的距离和，以及各时段的附加贡献；若某段时长为 $\Delta$，当时有 $p$ 个点，其中 $r$ 个向右，则这段附加贡献为 $\Delta r(p-r)$。

现在调整运动方式：各点仍在相同的时刻、相同的位置出现，每个时段向右运动的点数 $r$ 也保持不变，但把向右运动的任务交给位置最大的 $r$ 个点，其余点向左运动。每次有新点出现后，都可以重新分配方向。这样，一个点可能中途改变方向，但它始终以速度 $1/2$ 运动，运动总时长为自己的 $d_i$，最终偏离中点不会超过 $d_i/2$，所以最终位置一定还在所属区间内。

为了比较两个过程的得分，先比较它们的位置分布。把当前的位置数列分别记为 $x,y$，其中 $x$ 对应调整后的过程。设当前有 $p$ 个点，$X_q,Y_q$ 分别表示两边前 $q$ 大位置之和，并令 $X_0=Y_0=0$。我们始终有 $X_q\ge Y_q$，且全部位置之和相等，即 $X_p=Y_p$。这个关系在开始时成立。若接下来一段时长为 $\Delta$，其中 $r$ 个点向右，那么原过程前 $q$ 大位置之和至多增加 $\Delta(2\min(q,r)-q)/2$：任意 $q$ 个点中，至多有 $\min(q,r)$ 个向右。调整后的过程让最大的 $r$ 个点向右，位置顺序不会改变，所以前 $q$ 大位置之和恰好增加这么多，大小关系得以保持。新点出现时，两边加入同一个数；新的前 $q$ 大元素，要么来自旧的前 $q$ 大，要么来自旧的前 $q-1$ 大与这个新数，因此大小关系仍然保持。

由这个关系，可以比较新点出现时增加的得分。若新点的位置为 $c$，则它到已有点的距离和满足

$$ \sum_{i=1}^{p}|x_i-c| =pc-X_p+2\max_{0\le q\le p}(X_q-qc). $$

这里的最大值，就是所有正数 $x_i-c$ 的和；把它们取出，便得到上式。由于 $X_q\ge Y_q$ 且 $X_p=Y_p$，调整后的距离和不会更小。另一方面，在相邻两次新点出现之间，所有向左的点都在向右的点左边，同向点的距离不变，每对反向点的距离恰好增加 $\Delta$，真实得分便增加 $\Delta r(p-r)$，正好等于上界分数在这一时段的附加贡献。因此，调整后的最终真实得分不小于原来的上界分数。所有最终位置都在各自区间内，再用开头的凸性结论将它们改成端点，就得到一组得分不小于该上界分数的合法选择。这就证明了最大上界分数等于答案。长度相等的区间可以在同一时刻依次加入，长度为 $0$ 的区间在时刻 $0$ 加入，论证同样适用。

有了这个结论，就可以直接对上界分数做 DP。预处理 $A_i=\sum_{t>i}|L_i-L_t|$、$B_i=\sum_{t>i}|R_i-R_t|$。处理区间 $i$ 时，选左端点就一次加入 $A_i$，选右端点就一次加入 $B_i$，提前计入它与所有后续区间的基础贡献。两区间选择不同侧时的附加贡献，则等到后面的区间被处理时加入。

设 $f_{i,j}$ 表示处理完前 $i$ 个区间，其中 $j$ 个选右端点时，已经计入的贡献之和的最大值。这里已经计入了前 $i$ 个区间各自的 $A$ 或 $B$，以及前 $i$ 个区间内部所有不同侧物品对的附加贡献。初始化 $f_{0,0}=0$，其余状态为负无穷。对于 $0\le j<i$，转移为

$$ \begin{aligned} f_{i,j}&\gets\max\bigl(f_{i,j},f_{i-1,j}+A_i+d_i j\bigr),\\ f_{i,j+1}&\gets\max\bigl(f_{i,j+1},f_{i-1,j}+B_i+d_i(i-1-j)\bigr). \end{aligned} $$

第一条转移选择左端点，与之前的 $j$ 个右端点各产生 $d_i$ 的附加贡献；第二条选择右端点，与之前的 $i-1-j$ 个左端点各产生 $d_i$ 的附加贡献。处理完全部区间后，每对物品的基础贡献和附加贡献都恰好计算一次，答案就是 $\max_{0\le j\le k}f_{k,j}$。每一层只依赖上一层，可以用滚动数组实现。

复杂度分析

统计端点需要 $O(n)$ 时间，排序需要 $O(k\log k)$ 时间，预处理和 DP 均需要 $O(k^2)$ 时间，总时间复杂度为 $O(n+k^2)$。

代码保存了长度为 $n$ 的颜色数组，其余数组大小均为 $O(k)$，总空间复杂度为 $O(n+k)$。贡献和 DP 值需要使用 long long。

参考代码

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

using i64 = long long;

struct Interval {
    i64 l, r;
    i64 len() const { return r - l; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int &x : a) cin >> x;

    vector<Interval> seg(k + 1, {LLONG_MAX, LLONG_MIN});
    for (int i = 0; i < n; ++i) {
        i64 b;
        cin >> b;
        seg[a[i]].l = min(seg[a[i]].l, b);
        seg[a[i]].r = max(seg[a[i]].r, b);
    }
    sort(seg.begin() + 1, seg.end(), [](const Interval &x, const Interval &y) {
        return x.len() > y.len();
    });

    // 当前区间选左、右端点时，与所有后续区间的基础贡献。
    vector<i64> A(k + 1), B(k + 1);
    for (int i = 1; i <= k; ++i) {
        for (int t = i + 1; t <= k; ++t) {
            A[i] += abs(seg[i].l - seg[t].l);
            B[i] += abs(seg[i].r - seg[t].r);
        }
    }

    const i64 NEG = -(1LL << 62);
    vector<i64> dp(k + 1, NEG), ndp(k + 1, NEG);
    dp[0] = 0;
    for (int i = 1; i <= k; ++i) {
        fill(ndp.begin(), ndp.end(), NEG);
        i64 d = seg[i].len();
        // dp[j]：前 i-1 个区间中，j 个选择右端点。
        for (int j = 0; j < i; ++j) {
            if (dp[j] == NEG) continue;
            ndp[j] = max(ndp[j], dp[j] + A[i] + d * j);
            ndp[j + 1] = max(ndp[j + 1], dp[j] + B[i] + d * (i - 1 - j));
        }
        dp.swap(ndp);
    }
    cout << *max_element(dp.begin(), dp.end()) << '\n';
    return 0;
}