鏈接：https://ac.nowcoder.com/acm/contest/5672/A
來源：牛客網(wǎng)

題目描述
Nowadays, the Kingdom of Dreamgrid is suffering from a national pandemic. Fortunately, president Baobao is working effectively with the Center for Disease Control (CDC) and they are trying their best to make everything under control.

President Baobao has announced a policy of Social Distancing to prevent the diffusion of the virus. As the chief of CDC, you are required to research on the following problem:

There are $n$ people who need to be observed and you have already set a monitor in $(0,0)$ on a $2$-dimensional plane. Everyone should stay within the distance of r to the monitor. You also have to keep them stay away from each other as far as possible. To simplify the problem, you can only allocate them to integers coordinates.

Please maximize
${\sum }_{i=1}^{n?1}{\sum }_{j=i+1}^{n}d(i,j{)}^2$ ,
where $d(i,j)$ means the Euclidean distance between the $i$-th and the $j$-th person.
輸入描述:
There are multiple test cases. The first line of the input contains an integer $T$ $(1\le T\le 250)$ , indicating the number of test cases.

For each test case, the only line contains two integers $n,r$ $(1\le n\le 8,1\le r\le 30)$.
輸出描述:
Please output the answer in one line for each test case.
示例1

輸入 2 4 2 5 10 輸出 64 2496

設(shè)第$i$個點的橫坐標(biāo)為$x_i$，縱坐標(biāo)為$y_i$，則
$$\sum _{i=1}^{n?1}\sum _{j=i+1}^{n}d(i,j)=\sum _{i=1}^{n?1}\sum _{j=i+1}^n(x_i?x_j{)}^2+\sum _{i=1}^{n?1}\sum _{j=i+1}^n(y_i?y_j{)}^2$$
由于
$$\begin{array}{rl}\sum _{i=1}^{n?1}\sum _{j=i+1}^n(x_i?x_j{)}^2& =\sum _{i=1}^{n?1}\sum _{j=i+1}^n(x_i^2?2x_i{x}_j+x_j^2)\\ & =(n?1)\sum _{i=1}^n{x}_i^2?2\sum _{i=1}^{n?1}\sum _{j=i+1}^n{x}_i{x}_j\\ & =n\sum _{i=1}^n{x}_i^2?(\sum _{i=1}^n{x}_i^2+2\sum _{i=1}^{n?1}\sum _{j=i+1}^n{x}_i{x}_j)\\ & =n\sum _{i=1}^n{x}_i^2?(\sum _{i=1}^n{x}_i{)}^2\end{array}$$
因此$$\sum _{i=1}^{n?1}\sum _{j=i+1}^{n}d(i,j)=n\sum _{i=1}^n(x_i^2+y_i^2)?(\sum _{i=1}^n{x}_i{)}^2?(\sum _{i=1}^n{y}_i{)}^2$$
令$$dp[i][\sum x][\sum y]=max(\sum (x^2+y^2))$$
即$dp$表示當(dāng)前點數(shù)為$i$，所有點的橫坐標(biāo)之和為$\sum x$，縱坐標(biāo)之和為$\sum y$時所有點距離原點和$\sum (x^2+y^2)$的最大值。
狀態(tài)轉(zhuǎn)移方程為：
$$dp[i][\sum x][\sum y]=min(dp[i][\sum x][\sum y],dp[i?1][\sum x?x_j][\sum y?y_j]+(x_j^2+y_j^2))$$
對于圓的半徑$r$從小到大各$dp$一次。每次$dp$完，更新$$ans[i][r]=max(ans[i][r],i?dp[i][\sum x][\sum y]?(\sum x{)}^2?(\sum y{)}^2)$$

#include<bits/stdc++.h>using namespace std; const int base = 300; int dp[10][605][605], ans[10][35]; vector<pair<int, pair<int, int>>> seq; int now, T;int main() {for (int i = -30; i <= 30; ++i)for (int j = -30; j <= 30; ++j)seq.push_back({i * i + j * j, {i, j}});sort(seq.begin(), seq.end());memset(dp, -0x3f, sizeof(dp));dp[0][base][base] = 0;for (int r = 1; r <= 30; ++r) {while (seq[now].first <= r * r) {for (int i = 1; i <= 8; ++i)for (int x = base - r * i; x <= base + r * i; ++x)for (int y = base - r * i; y <= base + r * i; ++y)dp[i][x][y] = max(dp[i][x][y],dp[i - 1][x - seq[now].second.first][y - seq[now].second.second] + seq[now].first);now++;}for (int i = 1; i <= 8; ++i)for (int x = base - r * i; x <= base + r * i; ++x)for (int y = base - i * r; y <= base + r * i; ++y)if (dp[i][x][y] > 0)ans[i][r] = max(ans[i][r],i * dp[i][x][y] - ((x - base) * (x - base) + (y - base) * (y - base)));}scanf("%d", &T);while (T--) {int n, r;scanf("%d%d", &n, &r);printf("%d\n", ans[n][r]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Social Distancing的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。