Social Distancing_综合

链接：https://ac.nowcoder.com/acm/contest/5672/A
来源：牛客网

题目描述
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 \leq T \leq 250)$ , indicating the number of test cases.

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

设第 $i$ 个点的横坐标为 $x_i$ ，纵坐标为 $y_i$ ，则
$\sum_{i=1}^{n-1}\sum_{j=i+1}^nd(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{aligned} \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_ix_j+x_j^2) \\ &=(n-1)\sum_{i=1}^nx_i^2-2\sum_{i=1}^{n-1}\sum_{j=i+1}^nx_ix_j\\ &=n\sum_{i=1}^nx_i^2-(\sum_{i=1}^nx_i^2+2\sum_{i=1}^{n-1}\sum_{j=i+1}^nx_ix_j)\\ &=n\sum_{i=1}^nx_i^2-(\sum_{i=1}^nx_i)^2 \end{aligned}$
因此 $\sum_{i=1}^{n-1}\sum_{j=i+1}^nd(i,j)=n\sum_{i=1}^n(x_i^2+y_i^2)-(\sum_{i=1}^nx_i)^2-(\sum_{i=1}^ny_i)^2$
令 $dp[i][\sum x][\sum y]=max(\sum (x^2+y^2))$
即 $dp$ 表示当前点数为 $i$ ，所有点的横坐标之和为 $\sum x$ ，纵坐标之和为 $\sum y$ 时所有点距离原点和 $\sum (x^2+y^2)$ 的最大值。
状态转移方程为：
$dp[i][\sum x][\sum_{i=1}^ny_i]=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>#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define sc(a) scahf("%c",&a);
#define ss(a) scanf("%s",a)
#define pi(a) printf("%d\n",a)
#define pl(a) printf("%lld\n",a)
#define pc(a) putchar(a)
#define ms(a) memset(a,0,sizeof(a))
#define repi(i, a, b) for(register int i=a;i<=b;++i)
#define repd(i, a, b) for(register int i=a;i>=b;--i)
#define reps(s) for(register int i=head[s];i;i=Next[i])
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define pii pair<int,int>
#define mii unordered_map<int,int>
#define msi unordered_map<string,int>
#define lowbit(x) ((x)&(-(x)))
#define ce(i, r) i==r?'\n':' '
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define INF 0x3f3f3f3f
#define pr(x) cout<<#x<<": "<<x<<endl
using namespace std;inline int qr() {int f = 0, fu = 1;char c = getchar();while (c < '0' || c > '9') {if (c == '-')fu = -1;c = getchar();}while (c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + c - 48;c = getchar();}return f * fu;
}const int base = 300;
int dp[10][605][605], ans[10][35];
vector<pair<int, pii>> seq;
int now, T;int main() {repi(i, -30, 30)repi(j, -30, 30)seq.pb({i * i + j * j, {i, j}});sort(seq.begin(), seq.end());memset(dp, -0x3f, sizeof(dp));dp[0][base][base] = 0;repi(r, 1, 30) {while (seq[now].fi <= r * r) {repi(i, 1, 8)repi(x, base - r * i, base + r * i)repi(y, base - r * i, base + r * i)dp[i][x][y] = max(dp[i][x][y], dp[i - 1][x - seq[now].se.fi][y - seq[now].se.se] + seq[now].fi);now++;}repi(i, 1, 8)repi(x, base - r * i, base + r * i) repi(y, base - i * r, base + r * i)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)));}T = qr();while (T--) {int n = qr(), r = qr();pi(ans[n][r]);}return 0;
}