A-Social Distancing(dp打表)

题目链接：https://ac.nowcoder.com/acm/contest/5672/A
题目描述：
求在一个半径r的圆内整点上放置n个人，使得两两距离和最大。(n<=8 r<=30)
解题思路：
考虑dp打表，状态dp[i][j][k]为放置i个点，横坐标和为j，纵坐标和为k的每个点和圆心的的距离的平方和的最大值。为什么这样dp?
把题目中的公式先写出来：
由于减法不好维护，我们尝试转化为加法：

我们可以单独来看前面的xi^2+xj^2+yi^2+yj^2，它们可以写为(xi^2+yi^2)+(xj^2+yj^2)这个累加也就是在求所有的两两组合，每个出现n-1次，比如a、b、c，它们的组合有ab，ac，bc。a，b，c都各出现n-1次。后面的2xixj求累加，就是在求xixj的二元组合，我们知道(a+b+c)^2 = a^2+b^2+c^2+2ab+2ac+2bc,系数为2的就是xixj的组合。所以，我们可以把平方项给后面加上，凑成一个n元平方和，yiyj同理。
最后可以化成这样一个式子：