SocialDistancing - 题解

标签与难度

标签: 动态规划, 数学, 组合优化, 预处理, 背包问题, 计算几何难度: 2100

题目大意喵~

你好呀，指挥官！喵~ 我们接到了一个重要的任务：在梦之国度里，为了保持安全的社交距离，要把 $n$ 个人安置在一个二维平面上。

具体要求是这样的：

有一个监控器在原点 $(0,0)$ ，每个人都必须待在距离监控器 $r$ 的范围之内。也就是说，如果一个人在 $(x, y)$ ，那么必须满足 $x^2 + y^2 \le r^2$ 。
为了让大家尽可能地分开，我们需要最大化所有人之间两两距离的平方和。
所有人都必须被安置在整数坐标上，呐。

我们要找的就是这个最大的平方和~

输入:

多个测试用例。
每个用例包含两个整数 $n$ （人数，1 到 8）和 $r$ （半径，1 到 30）。

输出:

对每个用例，输出一个整数，表示最大的距离平方和。

解题思路分析

这道题看起来是要我们找 $n$ 个点，让它们互相之间尽可能地“散开”，喵~ "散开"的度量方式是所有点对之间距离的平方和。第一眼看到这个目标函数 $\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}d(i,j)^2$ 可能会觉得有点头大，因为它涉及到所有点对，直接优化似乎很困难。

但是不要怕，我们我最擅长把复杂的问题变简单啦！让我们来对这个式子进行一番魔法般的变形，看看能不能发现什么秘密，喵~

关键的数学推导

令第 $i$ 个人的坐标为 $P_i = (x_i, y_i)$ 。两点间的距离平方是 $d(i,j)^2 = (x_i - x_j)^2 + (y_i - y_j)^2$ 。我们要最大化的总和 $S$ 是：

S = \sum_{1 \le i < j \le n} d(i,j)^2 = \sum_{1 \le i < j \le n} \left( (x_i - x_j)^2 + (y_i - y_j)^2 \right)

这个式子可以拆成 $x$ 和 $y$ 两部分，它们是独立的。我们先只看 $x$ 部分， $S_x = \sum_{1 \le i < j \le n} (x_i - x_j)^2$ 。展开它：

S_x = \sum_{1 \le i < j \le n} (x_i^2 - 2x_i x_j + x_j^2)

让我们来数一数每个 $x_k^2$ 在这个和式里出现了多少次。对于一个特定的 $x_k^2$ ，它可以是式子里的 $x_i^2$ (当 $i=k$ 时) 或者 $x_j^2$ (当 $j=k$ 时)。无论哪种情况，另一个下标都可以在剩下的 $n-1$ 个里选。所以，每个 $x_k^2$ 都被加了 $n-1$ 次！于是，我们可以把所有 $x^2$ 项提出来：

S_x = (n-1) \sum_{k=1}^{n} x_k^2 - 2 \sum_{1 \le i < j \le n} x_i x_j

这个式子还是有点复杂，特别是那个交叉项 $x_i x_j$ 。不过，我们知道一个完全平方公式：

\left(\sum_{k=1}^{n} x_k\right)^2 = \sum_{k=1}^{n} x_k^2 + 2 \sum_{1 \le i < j \le n} x_i x_j

移项一下，就能得到：

2 \sum_{1 \le i < j \le n} x_i x_j = \left(\sum_{k=1}^{n} x_k\right)^2 - \sum_{k=1}^{n} x_k^2

把它代入回 $S_x$ 的表达式里：

S_x = (n-1) \sum_{k=1}^{n} x_k^2 - \left( \left(\sum_{k=1}^{n} x_k\right)^2 - \sum_{k=1}^{n} x_k^2 \right)

整理一下，就得到一个非常漂亮的式子啦！

S_x = n \sum_{k=1}^{n} x_k^2 - \left(\sum_{k=1}^{n} x_k\right)^2

$y$ 部分同理，所以总的平方和 $S$ 就是：

S = n \sum_{k=1}^{n} (x_k^2 + y_k^2) - \left( \left(\sum_{k=1}^{n} x_k\right)^2 + \left(\sum_{k=1}^{n} y_k\right)^2 \right)

这个公式是不是清爽多了？喵~ 它告诉我们，最终的结果只和三个量有关：

所有点坐标的平方和: $\sum (x_k^2 + y_k^2)$
所有点 $x$ 坐标的和: $\sum x_k$
所有点 $y$ 坐标的和: $\sum y_k$

动态规划登场！

有了这个简化的目标函数，问题就变成了一个组合优化问题：我们要从所有满足 $x^2+y^2 \le r^2$ 的整数点中，挑选出 $n$ 个点（可以重复挑选同一个点），使得 $n \cdot \sum (x_k^2+y_k^2) - ((\sum x_k)^2 + (\sum y_k)^2)$ 最大。

这听起来很像背包问题，不是吗？我们可以一个一个地放人，每次都记录下当前的状态。状态需要包含哪些信息呢？从我们的目标函数来看，就是上面提到的那几个和！

于是，我们可以定义一个 DP 状态： dp[i][sum_x][sum_y] 表示：放置了 i 个人之后，他们的 x 坐标总和为 sum_x，y 坐标总和为 sum_y 时，能得到的最大的坐标平方和 $\sum_{k=1}^{i} (x_k^2 + y_k^2)$ 。

状态转移: 当我们考虑放置第 i 个人时，我们可以从已经放置了 i-1 个人的所有状态进行转移。假设我们给第 i 个人选择了一个合法的坐标 (px, py) (即 $px^2+py^2 \le r^2$ )。如果之前 i-1 个人的状态是 dp[i-1][prev_sum_x][prev_sum_y]，那么加入新点后：

新的 x 坐标和是 sum_x = prev_sum_x + px
新的 y 坐标和是 sum_y = prev_sum_y + py
新的坐标平方和是 dp[i-1][prev_sum_x][prev_sum_y] + (px^2 + py^2)

所以，我们的状态转移方程就是： dp[i][sum_x][sum_y] = max(dp[i][sum_x][sum_y], dp[i-1][prev_sum_x][prev_sum_y] + px^2 + py^2)

一些实现细节:

坐标范围: sum_x 和 sum_y 可能是负数，所以我们需要给数组下标加一个偏移量（OFFSET）。一个点 x 的范围是 [-r, r]，n 个点的 sum_x 范围就是 [-n*r, n*r]。
DP表初始化: dp[0][OFFSET][OFFSET] = 0，表示0个人时，各项和都为0。其他所有状态初始化为一个极小值（比如-1），表示不可达。
预处理: 我们可以先找出所有在半径 r 内的合法整数点 (px, py)，存起来方便之后遍历。

最终答案: 当 DP 表格计算到 dp[n] 之后，我们就遍历所有可能的最终状态 dp[n][sum_x][sum_y]，代入我们的目标函数 $n \cdot (\text{value}) - (sum_x^2 + sum_y^2)$ ，找到其中的最大值就是答案啦！

关于复杂度: 这个 DP 的复杂度很高，大约是 $O(n \cdot (\pi r^2) \cdot (nr)^2)$ 。对于本题的 $n \le 8, r \le 30$ ，直接在每次查询时计算会超时。但注意到 $n$ 和 $r$ 的范围都很小，而且是多组测试数据。这强烈暗示我们可以预处理！也就是说，我们可以写一个程序，离线计算出所有可能的 $(n, r)$ 组合的答案，然后在提交的代码里直接查表输出。不过，作为一个教学题解，我会展示完整的 DP 计算过程，这样更能理解算法的精髓，喵~

代码实现

这是我根据上面的思路，精心重构的教学代码~ 注释很详细的哦！

cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

// 使用 long long 防止中间结果溢出，更安全喵~
using ll = long long;

// dp[i][sx][sy] 表示：
// 放置了 i 个人，x坐标和为 sx, y坐标和为 sy 时，
// 能达到的最大坐标平方和 sum(x_k^2 + y_k^2)
ll dp[9][501][501];

// 坐标和可能是负数，所以需要一个偏移量
const int OFFSET = 250; 

// 预先计算出所有在半径 r 内的合法点
vector<pair<int, int>> allowed_points;

void precompute_points(int r) {
    allowed_points.clear();
    for (int x = -r; x <= r; ++x) {
        for (int y = -r; y <= r; ++y) {
            if (x * x + y * y <= r * r) {
                allowed_points.push_back({x, y});
            }
        }
    }
}

ll solve(int n, int r) {
    if (n == 0) {
        return 0;
    }

    precompute_points(r);

    // 初始化DP表，-1表示状态不可达
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j < 2 * OFFSET; ++j) {
            for (int k = 0; k < 2 * OFFSET; ++k) {
                dp[i][j][k] = -1;
            }
        }
    }

    // 初始状态：0个人，所有和都为0，坐标平方和也为0
    dp[0][OFFSET][OFFSET] = 0;

    // 开始DP！一层一层地放置人
    for (int i = 0; i < n; ++i) {
        int max_coord_sum = i * r;
        for (int sx = -max_coord_sum; sx <= max_coord_sum; ++sx) {
            for (int sy = -max_coord_sum; sy <= max_coord_sum; ++sy) {
                // 如果当前状态不可达，就跳过
                if (dp[i][sx + OFFSET][sy + OFFSET] == -1) {
                    continue;
                }

                // 尝试添加一个新的点 (px, py)
                for (const auto& p : allowed_points) {
                    int px = p.first;
                    int py = p.second;

                    int next_sx = sx + px;
                    int next_sy = sy + py;
                    
                    ll current_sum_sq = dp[i][sx + OFFSET][sy + OFFSET];
                    ll new_sum_sq = current_sum_sq + px * px + py * py;

                    // 更新下一个状态
                    ll& next_dp_val = dp[i + 1][next_sx + OFFSET][next_sy + OFFSET];
                    next_dp_val = max(next_dp_val, new_sum_sq);
                }
            }
        }
    }

    // DP完成，计算最终答案
    ll max_total_sum_sq = 0;
    int final_max_coord_sum = n * r;
    for (int sx = -final_max_coord_sum; sx <= final_max_coord_sum; ++sx) {
        for (int sy = -final_max_coord_sum; sy <= final_max_coord_sum; ++sy) {
            if (dp[n][sx + OFFSET][sy + OFFSET] != -1) {
                ll sum_sq = dp[n][sx + OFFSET][sy + OFFSET];
                ll current_total = (ll)n * sum_sq - ((ll)sx * sx + (ll)sy * sy);
                max_total_sum_sq = max(max_total_sum_sq, current_total);
            }
        }
    }

    return max_total_sum_sq;
}

int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        int n, r;
        cin >> n >> r;
        cout << solve(n, r) << "\n";
    }

    return 0;
}

复杂度分析

时间复杂度: $O(T \cdot (n \cdot (\pi r^2) \cdot (nr)^2))$ 。其中 $T$ 是测试用例数量。
- 外层循环是人数 $n$ (从 0 到 $n-1$ )。
- DP状态遍历是 $O((nr)^2)$ ，因为 sum_x 和 sum_y 的范围都和 $i \cdot r$ 相关。
- 每次状态转移，需要遍历所有合法点，数量约为 $\pi r^2$ 。
- 综合起来，对于单次 solve(n, r) 调用，复杂度是 $O(n^3 r^4)$ 级别的，非常高。这就是为什么说这题适合预处理。在比赛中，可以先用这个程序把所有 ans[n][r] 的值算出来，然后提交一个查表版的代码。
空间复杂度: $O(n \cdot (nr)^2) = O(n^3 r^2)$ 。
- 主要是 DP 表 dp[9][501][501] 占用的空间。
- allowed_points 向量的空间是 $O(r^2)$ 。
- DP 表是空间占用的主导部分。

知识点总结

这道题真是一次有趣的冒险，喵！我们来总结一下学到了什么吧：

目标函数变形: 这是解题的钥匙！将复杂的 $\sum d(i,j)^2$ 转化为 $n \sum |P_k|^2 - |\sum P_k|^2$ 的形式，是典型的数学技巧，在很多问题中都有应用。它将一个依赖于“点对”的量，转化为了只依赖于“点集”整体属性的量。
动态规划 (DP): 变形后的问题结构完美地契合了 DP。我们学会了如何根据目标函数来设计 DP 的状态，这个状态需要包含所有计算最终结果所必需的信息。
背包思想: 这个 DP 本质上是一个多维背包问题。我们有 $n$ 个“容量”（要选 $n$ 个人），物品就是所有合法的坐标点。每个物品有三个“代价”或“属性”（ $px, py, px^2+py^2$ ），我们要优化的就是这些属性的某个组合。
预处理/打表: 对于输入范围小、查询次数多的题目，要有机智地想到“打表”这个技巧。离线运行一个高复杂度的程序生成答案，在线直接查询，是一种非常实用的竞赛策略。

希望这篇题解能帮到你，喵~ 如果还有不懂的地方，随时可以再来问我哦！一起加油，攻克更多的难题吧！

SocialDistancing - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

关键的数学推导 ​

动态规划登场！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​