标签归档：DP

迎春舞会之集体舞

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;
}

棋盘制作

1条回复

【问题描述 】
国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个8*8大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。

而我们的主人公小Q，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。

小Q找到了一张由N*M个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种颜色之一。小Q想在这种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。

不过小Q还没有决定是找一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相间，即相邻的格子不同色），所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决定哪个更好一些。

于是小Q找到了即将参加全国信息学竞赛的你，你能帮助他么？

【输入格式 Input Format 】
第一行包含两个整数N和M，分别表示矩形纸片的长和宽。接下来的N行包含一个N * M的01矩阵，表示这张矩形纸片的颜色（0表示白色，1表示黑色）。

【输出格式 Output Format】
包含两行，每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积，第二行为可以找到的最大矩形棋盘的面积（注意正方形和矩形是可以相交或者包含的）。

【样例输入 Sample Input】
3 3
1 0 1
0 1 0
1 0 0

【样例输出 Sample Output】
4
6

注释 Hint
对于20%的数据，N, M ≤ 80
对于40%的数据，N, M ≤ 400
对于100%的数据，N, M ≤ 2000

算法分析
和盖房子那道题目差不多吧.

正方形是一样的.只不过是重新开始的判断条件不同

长方形记录长和宽就好了.

【代码】

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

#include <stdio.h>
#include <string.h>
#define MAXN 2001
int a[MAXN][MAXN], f[MAXN][MAXN], c[MAXN][MAXN], r[MAXN][MAXN];
 
int min(int t1, int t2)
{
        return t1<t2?t1:t2;
}
 
int main()
{
        int n, m, i, j, k, maxf = 0, maxc = 0, maxr = 0, s1, s2;
 
        scanf("%d%d", &n, &m);
 
        memset(f, 0, sizeof(f));
        memset(c, 0, sizeof(c));
 
        for (i = 1; i <= n; i++)
        {
               for (j = 1; j <= m; j++)
                      scanf("%d", &a[i][j]);
        }
 
        for (i = 1; i<= n; i++)
               f[i][1] = 1;     
 
        for (i = 1; i <= m; i++)
               f[1][i] = 1;
 
        for (i = 2; i <= n; i++)    //求正方形的连长
        {
               for (j = 2; j<= m; j++)
               {
                      if (a[i - 1][j] != a[i][j] && a[i][j - 1] != a[i][j])
                      {
                             f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
                      }
                      else
                      {
                             f[i][j] = 1;
                      }
 
                      if (f[i][j] > maxf)
                             maxf = f[i][j];
               }
        }
 
        c[1][1] = 1;    
        r[1][1] = 1;      //长宽初始化
 
        for (i = 2; i <= m; i++)
        {
               if (a[1][i] != a[1][i - 1])
               {
                      c[1][i] = c[1][i - 1] + 1;
               }
               else
                      c[1][i] = 1;
               r[1][i] = 1;
        }
 
        for (i = 2; i <= n; i++)
        {
               if (a[i][1] != a[i - 1][1])
               {
                      r[i][1] = r[i - 1][1] + 1;
               }
               else
                      r[i][1] = 1;
 
               c[i][1] = 1;
        }
 
        for (i = 2; i <= n; i++)
        {
               for (j = 2; j<= m; j++)
               {
                      if (a[i - 1][j] != a[i][j] && a[i][j - 1] != a[i][j])
                      {
                             s1 = min(c[i][j - 1] + 1, c[i - 1][j]) * (r[i - 1][j] + 1);
                             s2 = min(r[i - 1][j] + 1, r[i][j - 1]) * (c[i][j - 1] + 1);
 
                             if (s1 > s2)
                             {
                                    r[i][j] = r[i - 1][j] + 1;
                                    c[i][j] = min(c[i][j - 1] + 1, c[i - 1][j]);
                             }
                             else
                             {
                                    c[i][j] = c[i][j - 1] + 1;
                                    r[i][j] = min(r[i - 1][j] + 1, r[i][j - 1]);
                             }
                      }
                      else
                      {
                             if (a[i - 1][j] != a[i][j])
                             {
                                    r[i][j] = r[i - 1][j] + 1;
                                    c[i][j] = 1;
                             }
                             else if (a[i][j - 1] != a[i][j] )
                             {
                                    r[i][j] = 1;
                                    c[i][j] = c[i][j - 1] + 1;
                             }
                             else
                             {
                                    r[i][j] = 1;
                                    c[i][j] = 1;
                             }
                      }
 
                      if (r[i][j] * c[i][j] > maxr * maxc)
                      {
                             maxr = r[i][j];
                             maxc = c[i][j];
                      }
               }
        }
 
        printf("%d\n%d\n", maxf * maxf, maxr * maxc);
        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;
}