点集分组最小极差(Simple Grouping) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const long long INF = (1LL << 62);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<long long> x(n), y(n);
    for (int i = 0; i < n; ++i) cin >> x[i] >> y[i];
    int tot = 1 << n;
    vector<long long> cost(tot, 0);
    for (int mask = 1; mask < tot; ++mask) {
        long long mx = 0;
        for (int i = 0; i < n; ++i) {
            if (!((mask >> i) & 1)) continue;
            for (int j = i + 1; j < n; ++j) {
                if (!((mask >> j) & 1)) continue;
                long long dx = x[i] - x[j];
                long long dy = y[i] - y[j];
                mx = max(mx, dx * dx + dy * dy);
            }
        }
        cost[mask] = mx;
    }
    vector<long long> dp(tot, INF), ndp(tot, INF);
    dp[0] = 0;
    for (int step = 1; step <= k; ++step) {
        fill(ndp.begin(), ndp.end(), INF);
        for (int mask = 1; mask < tot; ++mask) {
            for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
                long long val = max(dp[mask ^ sub], cost[sub]);
                if (val < ndp[mask]) ndp[mask] = val;
            }
        }
        dp.swap(ndp);
    }
    cout << dp[tot - 1] << "\n";
    return 0;
}