标签归档:DP

迎春舞会之集体舞

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

棋盘制作

【问题描述 】
国际象棋是世界上最古老的博弈游戏之一,和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想,棋盘是一个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;
}