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