2020牛客暑期多校训练营（第七场）A Social Distancing

题目大意

在半径为 $r$ 的圆内放 $n$ 个人，使得相互之间距离尽可能远，即使得 $\sum_{i=1}^{n-1}\sum_{j=i+1}^nd(i,j)^2$ 尽可能大， $d(i,j)$ 表示第i个人与第j个人的欧几里得距离。

解题思路

这道题我们考虑用dp来做。很容易得出，我们的n个点的距离和为：

$\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}(x_i-x_j)^2+(y_i-y_j)^2$
将其化为加法，可以推出这样的式子：

$n×\sum_{i=1}^n{x_i}^2+{y_i}^2-(\sum_{i=1}^n{x_i}^2+{y_i}^2)$
每次直接求出前面一项，而后面用勾股定理求即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
int dp[10][610][610],ans[40][40];
vector<pair<int,pair<int,int> > > v;
int main()
{
    int t,n,m,s=0,i,j,k,l;
    for(i=-32;i<=32;i++)
        for(j=-32;j<=32;j++)
            v.push_back((make_pair)(i*i+j*j,make_pair(i,j)));
    for(i=0;i<9;i++)
        for(j=0;j<600;j++)
            for(k=0;k<600;k++)
                dp[i][j][k]=-2e9;
    dp[0][300][300]=0;
    sort(v.begin(),v.end());
    for(i=1;i<=30;i++) 
    {
        while(v[s].first<=i*i)
        {
            for(j=1;j<=8;j++)
                for(k=300-i*j;k<=300+i*j;k++)
                    for(l=300-i*j;l<=300+i*j;l++)
                        dp[j][k][l]=max(dp[j][k][l],dp[j-1][k-v[s].second.first][l-v[s].second.second]+v[s].first);
            s++;
        }
        for(j=1;j<=8;j++)
            for(k=0;k<600;k++)
                for(l=0;l<600;l++)
                    if(dp[j][k][l]>0)
                         ans[j][i]=max(ans[j][i],j*dp[j][k][l]-((k-300)*(k-300)+(l-300)*(l-300)));
    }
    scanf("%d",&t);
    while(t--) scanf("%d%d",&n,&m),printf("%d\n",ans[n][m]);
    return 0;
}