题目
T(T<=250)组样例，每次给出一个圆的半径r(r<=30)，
在圆上和圆内放置n个整点，要求的最大值。
其中d(i,j)表示i和j之间的距离。即求所有点的距离的平方和的最大值。
思路来源
https://blog.csdn.net/zhangchizc/article/details/107746793
题解
把和分开考虑，不妨只考虑这一维
考虑这是一个矩阵的上三角矩阵(略有不同，此处对角线均为0)
对于任意一个数来说，其与的j都出现过一次对，代表
二者乘积是，把xi这项凑足，同时记，
则有每个i对答案的贡献是，
可以理解为平方项二倍展开，上三角矩阵只有一半，所以把2除掉
且注意到出现在个对里，平方项贡献是
即化简为
感觉这个套路见过很多次了，然而想不到要这么dp，
于是就化简为
令dp[i][j][k]表示选了i个点，sumx=j，sumy=k（把后两项固定住）时的最大第一项
则实际答案为i*dp[i][j][k]-j*j-k*k，具体实现时将点按半径r的增序更新，即可更新ans[i][r]，
O(1e9)预处理，O(1)回答，5s还可以吧，要是实在太慢就打表
代码
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=64*64+5,off=300;
//dp[i][j][k]表示选i个点 sumx=j sumy=k时 的 最大的平方项代价之和
int t,n,d,dp[9][610][610],ans[9][32],c;
struct node{int d,x,y;bool operator<(node &x)const{return d<x.d;}
}e[N];
int main(){for(int x=-32;x<=32;++x){for(int y=-32;y<=32;++y){e[++c]=node{x*x+y*y,x,y};}}sort(e+1,e+c+1);memset(dp,128,sizeof dp);dp[0][off][off]=0;int now=1;for(int r=1;r<=30;++r){while(now<=c && e[now].d<=r*r){for(int i=1;i<=8;++i){for(int j=-r*i;j<=r*i;++j){//i个点 abs(sumx) 不可能超过i*rfor(int k=-r*i;k<=r*i;++k){dp[i][j+off][k+off]=max(dp[i][j+off][k+off],dp[i-1][j-e[now].x+off][k-e[now].y+off]+e[now].d);}}}now++;}for(int i=1;i<=8;++i){for(int j=-r*i;j<=r*i;++j){for(int k=-r*i;k<=r*i;++k){if(dp[i][j+off][k+off]>0){ans[i][r]=max(ans[i][r],dp[i][j+off][k+off]*i-j*j-k*k);}}}}}scanf("%d",&t);while(t--){scanf("%d%d",&n,&d);printf("%d\n",ans[n][d]);}return 0;
}