迎春舞会之三人组舞

【问题描述】
背景 Background
  HNSDFZ的同学们为了庆祝春节,准备排练一场舞

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

【输入格式 Input Format】
  第一排为m,n。
  第二排n个数字,保证升序排列。

【输出格式 Output Format】
  输出最小“残疾程度”。

【样例输入 Sample Input】
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

【样例输出 Sample Output】
23

注释 Hint
m<=1000,n<=5000 数据保证3*m<=n 【算法分析】 从大到小排序 a[i] f[i,j] 表示前i个数中有j对跳舞组合时的最优解 应为要最优就必须是排序时相邻两数的在两边才最好 而中间的人最高,记 f[i,j]=f[i-2,j-1]+(a[i]-a[i-1])^2 如果不取a[j]就 记 f[i,j]=f[i-1,j] 所以 f[i,j]=min{f[i,j]=f[i-2,j-1]+(a[i]-a[i-1])^2 | f[i,j]=f[i-1,j]} huyichen 摘自一大牛语录: 首先将筷子长度从短到长排序。 F[i,j,0]表示i个人使用前j双筷子,且第j根筷子不用,所需要长度差的平方和的最小值。 F[i,j,1]表示i个人使用前j双筷子,且使用第j根筷子,所需要长度差的平方和的最小值。 则F[i,j,0]=min{f[i,j-1,1],f[i,j-1,0]},F[i,j,1]=F[i-1,j-1,0]+(l[j]-l[j-1])^2 ans=min{F[k,n,1],F[k,n,0]} 算法复杂度为O(NK)。 算法正确性的简单证明: 因为筷子配对的时候要求是长度平方差最小,所以每根筷子的配对的时候总是希望和长度差最小的配对,即排序后相邻两根筷子是可以配对的。l[a],l,l[c],l[d]表示4根排序好的筷子。因为(l-l[a])^2+(l[d]-l[c])^2<(l-l[c])^2+(l[d]-l[a])^2,所以上述配对方法是正确的。 本题同样可以把模型直接转变为二分图最小权匹配。 将两根筷子相连的边权值标记为两根筷子长度平方差,然后对二分图求一次最小权匹配。可以使用网络流的最小费用K流的算法,寻找K次最短路的增广轨。 算法复杂度为O(KN^3)。 非常显然,动态规划的复杂度远远低于二分图最小权匹配的复杂度。 【代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <string.h>
 
int a[1001][5001];
int b[5001];
 
int main()
{
       int n, m, i, j, k, temp;
 
       scanf("%d%d", &m, &n);
       memset(b, 0, sizeof(b));
 
       for (i = 1; i <= n; i++)
              scanf("%d", &b[i]);
 
       for (i = 0; i <= m; i++)
       {
              for (j = 0; j <= n; j++)
                     a[i][j] = 2000000000;
       }
 
       for (i = 0; i <= n; i++)
              a[0][i] = 0;
 
       for (i = 1; i <= m; i++)
       {
              for (j = i + i; j <= n - (m - i) * 3; j++)
              {
                     a[i][j] = a[i][j - 1];
                     temp = a[i - 1][j - 2] + (b[j] - b[j - 1]) * (b[j] - b[j - 1]);
                     if ( j < n - (m - i) * 3 && temp < a[i][j])
                            a[i][j] = temp;
              }
       }
 
       printf("%d\n", a[m][n]);
       return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注


*

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>