B4373 [GXPC-S 2025] 队伍集结 / team 题解

Lyw_and_Segment_Tree · 2025-08-06 16:43:06 · 题解

一眼题，但是细节很多。

首先我们按照点的坐标从左往右依次标号为 1, 2, 3, \dots, k。

设 dp_{i, j} 表示把第 i 个点放在 j 位置能得到的答案，可以枚举第 i - 1 个点位置 t，则有 dp_{i, j} = \min(dp_{i - 1, t} + cost(t, j))，其中 cost(x, y) 表示 x 到 y 这段区间内，学生不满意度的和。

所以我们需要枚举 i, j, k 算出所有 dp 值，注意边界条件 dp_{0, 0} = 0，其余的先设为 \text{INF}，这里的时间复杂度是 O(k\max(a_i) ^ 2)。

但是，这样还没有做完，考虑第 k 个点右侧可能还有学生没有被计算到，所以我们还需要一个函数 costt(x) 来算出 [x, \max(a_i)] 这段区间中学生不满意度之和。

综上，有：

ans = \min_{i = 0}^{\max{a_i}}(dp_{k, i} + costt(i))

把这个 ans 算出来即可。

这样本题看似做完了，实则细节比较多，你需要注意的细节：

在算 dp 值的时候要特判 i = 1，这时 cost 函数的计算方法也有变化，可以考虑加上一个参数表示是否是这种情况，进行分讨。
在算 dp 值的时候 j 最小可以是 0，t 可以取到 j，这里需要特别注意，如果你不慎把 j 的起点设为 1 从而获得 60 pts 可能是这个原因。
要先对 a_i 排序，否则无法计算。
其他神秘的细节，似乎没了。

所以最后的时间复杂度主要来源于计算 dp 数组，时间复杂度 O(k \max(a_i) ^ 2)。

code：

#include <bits/stdc++.h>
#define ll long long
#define db double
#define vec vector
#define pb push_back
#define pll pair<ll, ll>
#define pr pair
#define mkp make_pair
#define endl "\n"

using namespace std;

const ll mod = 998244353;

namespace fastio {char buf[1 << 21], *p1 = buf, *p2 = buf; const ll getc() {return p1 == p2 && ( p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1 ++;}const ll read() {ll x = 0, f = 1;char ch = getc();while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getc();}while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48), ch = getc();}return x * f;} const void write(ll x) {if (x < 0) { putchar('-'), x = -x; } ll sta[35], top = 0; do {sta[top++] = x % 10, x /= 10;} while (x); while (top) putchar(sta[--top] + 48); }}

#define rd fastio::read
#define wt fastio::write
#define gc fastio::getc

ll n, m, q, k, dp[205][305]; // string s;

ll opt, l, r, x, y, z, ans = 1e18;

struct node {
    ll a, b;

    friend bool operator < (node x, node y) {
        return x.a < y.a;
    }
} a[200005] ;

ll cost(ll x, ll y, bool f) {
    if (x > y) swap(x, y);

    ll res = 0;

    for (ll i = 1; i <= n; i++) {
        if (a[i].a >= x && a[i].a <= y) {
            ll ps = min(a[i].a - x, y - a[i].a);

            if (x == 0 && !f) ps = y - a[i].a; 

            res += ps * ps * a[i].b; 
        }
    }

    return res;
}

ll costt(ll x) {
    ll res = 0;

    for (ll i = 1; i <= n; i++) {
        if (a[i].a >= x) {
            res += (a[i].a - x) * (a[i].a - x) * a[i].b;
        }
    }

    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    ll i, j, u, v, w, q, res = 0, now;

    cin >> n >> k; ll mxa = 0;

    for (i = 1; i <= n; i++) cin >> a[i].a >> a[i].b, mxa = max(mxa, a[i].a);

    sort(a + 1, a + n + 1);

    memset(dp, 63, sizeof(dp));

    dp[0][0] = 0;

    for (i = 1; i <= k; i++) {
        for (j = 0; j <= mxa; j++) {            
            for (ll t = 0; t <= j; t++) {
                if (i == 1) {
                    dp[i][j] = min(dp[i][j], dp[i - 1][0] + cost(0, j, 0));
                } else {
                    dp[i][j] = min(dp[i][j], dp[i - 1][t] + cost(t, j, 1));
                }
            }
        }
    }

    for (i = 0; i <= mxa; i++) {
        ans = min(ans, dp[k][i] + costt(i));
    }

    cout << ans;

    return 0;
}

/*
dp[i][j] 表示第 i 个点设在 j 位置的答案

dp[i][j] = min(dp[i - 1][t] + w(t, j))

2 1
3 3
10 2

59
*/

AC record