n个人选出3*m人,排成m组,每组3人.
站的队形 -  - 较矮的2个人站两侧,最高的站中间.
从对称学角度来欣赏,左右两个人的身高越接近,则这一组的"残疾程度"越低.
计算公式为 h=(a-b)^2 (a,b为较矮的2人的身高)
现在候选人有n个人,要从他们当中选出3*m个人排舞蹈,要求总体的"残疾程度"最低.
对于这道题,首先应该想到贪心:每次取差值最小的一对.但是这样的贪心策略很容易找到反例,而且N=5000的数据规模,十分有可能是O(n^2)的算法.
于是考虑动态规划.如果是DP,那么很容易想到如下的状态定义:d[i][j]表示用前j个数组成i个(xyz)数对的最小消耗.
另外一个很容易注意到的地方就是:对于一个最优决策中的任意一个数对(xyz),其中x和y必在有序的a[i]中相邻.关于这点用反证法不难证明,也很容易注意到.
对于(xyz)中的z应该如何决策的问题,之前一直令我迷惑,这一点应该是题目最难解决的问题.
这应该不难理解,但是对于z的决策呢?
如果把a[i]按降序排列,那么z的影响就可以忽略了!这样依然可以采用上面的方程.
如果j<3i,此时当前策略是不可行的,d[i][j]=INF;
若d[i][j-1]为有效状态,可以继续递归地进行下去.