问题 2133. -- 迎春舞会之三人组舞

2133: 迎春舞会之三人组舞

时间限制: 0 Sec  内存限制: 128 MB
提交: 0  解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

        n个人选出3*m人，排成m组，每组3人。
        站的队形——较矮的2个人站两侧，最高的站中间。
        从对称学角度来欣赏，左右两个人的身高越接近，则这一组的“残疾程度”越低。
        计算公式为    h=(a-b)^2    (a、b为较矮的2人的身高)
        那么问题来了。
        现在候选人有n个人，要从他们当中选出3*m个人排舞蹈，要求总体的“残疾程度”最低。

输入 [ycwhzsrzw.in]

        第一排为m，n。
        第二排n个数字，保证升序排列。

输出 [ycwhzsrzw.out]

        输出最小“残疾程度”。

样例输入

9 40
1 8 10 16 19 22 27 33 36 40 47 52 56 61 63 71 72 75 81 81 84 88 96 98 103 110 113 118 124 128 129 134 134 139 148 157 157 160 162 164

样例输出

23

提示

m< =1000,n< =5000
数据保证3*m< =n

标签

提高一等 动态规划 迎春舞会 VIJOS

[上一题][提交][讨论版][状态][下一题]