标签归档：ACM

迎春舞会之三人组舞

发表回复

【问题描述】
背景 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;
}

迎春舞会之集体舞

1条回复

【问题描述】
背景 Background
　　HNSDFZ的同学们为了庆祝春节，准备排练一场舞会。
【描述 Description 】
　　表演者排成n排，构成一个向前的正三角形（在屏幕上,即向下）。而就每个人，他有可能正面朝前（小的向前正三角形）、或向后三角形（小的向后正三角形）。
　　然而这些人在服装上有明显区别——一部分穿冬季校服，其他的穿夏季校服。
　　现在给出每个人的着衣情况，请你求穿夏季校服的同学所构成的最大正三角形,输出所含人数。

输入格式 Input Format
　　第一排为n。
　　接下来n排，第i排有2*i-1个有效字符（‘#’或‘-’，分别表示此同学穿冬季校服或穿夏季校服）。输入文件中出现空格，且空格只是为了保持整个三角形的形状。

【输出格式 Output Format】
　　输出人数。

【样例输入 Sample Input】
5
#-##—-#
—–#-
—#-
-#-
-

样例输出 Sample Output
9

注释 Hint
n<=100 【算法分析】 对于三角形有两种情况： 尖向下时： f1[i][j]+=min(f1[i-1][j-1],f1[i-1][j],f1[i-1][j+1]) 尖向上时： f2[i][j]+=min(f2[i+1][j-1],f2[i+1][j],f2[i+1][j-1]) 而且一定要仔细看题目给的三角形 　　“他有可能正面朝前（小的向前正三角形）、或向后三角形（小的向后正三角形）” 注意几点： 1.尖向上的情况，只能是一行中的偶数个 2.尖向下的情况，只能是一行中的奇数个 代码 

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#include <stdio.h>
#include <string.h>
 
#define min(a,b) a<b?a:b
 
int main()
{
       char ch[300][300];
       int f[300][300];
       int n, i, j, k, flag, max = 1, len;
 
       scanf("%d", &n);
       getchar();
 
       for (i = 0; i < n; i++)
       {
              gets(ch[i]);
       }
 
       memset(f, 0, sizeof(f));
       j = 0;
 
       while (ch[0][j] == ' ')
              j++;
 
       k = 1;
 
       while (j < strlen(ch[0]))
       {
              if (ch[0][j] == '#')
                     f[0][k++] = 0;
              else if (ch[0][j] == '-')
                     f[0][k++] = 1;
              j++;
       }
       for (i = 1; i < n; i++)
       {
              j = 0;
              while (ch[i][j] == ' ')
                     j++;
 
              k = i;
              flag = 0;
 
              while (ch[i][j] != '\0')
              {
                     if (ch[i][j] != ' ')
                     {
                            flag++;
                            k++;
 
                            if (ch[i][j] == '-')
                            {
                                   f[i][k] = 1;
                                   if (flag % 2 == 1)  //向下的三角形
                                   {
                                          if (f[i - 1][k] != 0 && f[i - 1][k - 1] != 0 && f[i - 1][k + 1] != 0)
                                          {
                                                 f[i][k] += min(f[i - 1][k - 1], f[i - 1][k + 1]);
                                          }
                                   }
                                   else  //向上的三角形
                                   {
                                          if (f[i][k - 1] != 0 && f[i][k - 2] != 0 && f[i - 1][k - 1] != 0)
                                          {
                                                 f[i][k] += min(f[i][k - 2], f[i - 1][k - 1]);
                                          }                                 
                                   }
 
                                   if (f[i][k] > max)
                                          max = f[i][k];
                            }
                     }
                     j++;
              }
       }
 
       printf("%d\n", max * (max * 2 -1 + 1) / 2);
       return 0;
}

盖房子

发表回复

【问题描述】
永恒の灵魂最近得到了面积为n*m的一大块土地（高兴ING^_^），他想在这块土地上建造一所房子，这个房子必须是正方形的。
但是，这块土地并非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。这些瑕疵十分恶心，以至于根本不能在上面盖一砖一瓦。
他希望找到一块最大的正方形无瑕疵土地来盖房子。
不过，这并不是什么难题，永恒の灵魂在10分钟内就轻松解决了这个问题。
现在，您也来试试吧。

【输入格式 Input Format】
输入文件第一行为两个整数n,m（1<=n,m<=1000），接下来n行，每行m个数字，用空格隔开。0表示该块土地有瑕疵，1表示该块土地完好。 【输出格式 Output Format】 一个整数，最大正方形的边长。 【样例输入 Sample Input】 4 4 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 【样例输出 Sample Output 】 2 【算法分析】 状态方程就是.f[i,j]=min{f[i-1,j],f[i,j-1],f[i-1,j-1]}+1; f[i,j]表示的是 右下角坐标为(i,j)的正方形边长是f[i,j] 只要从左到右从上到下的2重循环就可以解决叻. 应该容易理解吧. 就贴一下Example Date运行后的F数组值 0 1 1 1 1 1 2 0 0 1 2 0 1 1 0 1 【代码】 

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
40
41

#include <stdio.h>
#include <string.h>
int a[1002][1002], f[1002][1002];
 
int main()
{
       int i, j, n, m, max = -1;
 
       scanf("%d%d", &n, &m);
       memset(a, 0, sizeof(a));
       memset(f, 0, sizeof(f));
 
       for (i = 1; i <= n; i++)
              for (j = 1; j <= m; j++)
                     scanf("%d", &a[i][j]);
 
              for (i = 1; i <= n; i++)
              {
                     for (j = 1; j <= n; j++)
                     {
                            if (a[i][j] == 1)
                            {
                                          f[i][j] = f[i - 1][j];
                                          if (f[i][j] > f[i][j - 1])
                                                 f[i][j] = f[i][j - 1];
 
                                          if (f[i][j] > f[i - 1][j - 1])
                                                 f[i][j] = f[i - 1][j - 1];
                                          f[i][j] = f[i][j] + 1;
                            }
                            else
                                   f[i][j] = a[i][j];
 
                            if (f[i][j] > max)
                                   max = f[i][j];
                     }
              }
 
              printf("%d\n", max);
              return 0;
}