Description
It is always very nice
to have little brothers or sisters. You can tease them, lock them in the
bathroom or put red hot chili in their sandwiches. But there is also a time when
all meanness comes back!
As you know, in one month it is Christmas and this
year you are honored to make the big star that will be stuck on the top of the
Christmas tree. But when you get the triangle-patterned silver paper you
realize that there are many holes in it. Your little sister has already cut out
smaller triangles for the normal Christmas stars. Your only chance is to find
an algorithm that tells you for each piece of silver paper the size of the
largest remaining triangle.
Given a triangle structure with white and black
fields inside you must find the largest triangle area of white fields, as shown
in the following figure.
Input
The input contains
several triangle descriptions. The first line of each description contains an
integer n (1 <= n <= 100), which gives the height of the triangle. The
next n lines contain characters of the set {space, #, -} representing the rows
of the triangle, where `#‘ is a black and `-‘ a white field. The spaces are
used only to keep the triangle shape in the input by padding at the left end of
the lines. (Compare with the sample input. The first test case corresponds to
the figure.)
For each triangle, the number of the characters `#‘ and `-‘
per line is odd and decreases from 2n - 1 down to 1.
The input is
terminated by a description starting with n = 0.
Output
For each triangle in
the input, first output the number of the triangle, as shown in the sample
output. Then print the line "The largest triangle area is a.", where a is the
number of fields inside the largest triangle that consists only of white fields.
Note that the largest triangle can have its point at the top, as in the second
case of the sample input.
Output a blank line after each test
case.
Sample Input
5
#-##----#
-----#-
---#-
-#-
-
4
#-#-#--
#---#
##-
-
0
Sample Output
Triangle #1
The largest triangle area is 9.
Triangle #2
The largest triangle area is 4.
Source
今天组队练习的题目，cjx因为要赶学校所以就木有做了。跟想的一样应该用dp。暴力应该也可以。
当n=5时：
1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7
0 0 1 2 3 4 5
0 0 0 1 2 3
0 0 0
0 1
因为输入的前面有空格所以要+k
(1->((n-i+1)*2-1)+k) i=[1...n]
输入：
0
1 0 0 1 1 1 1 0
1 1 1 1 1 0 1
1 1 1 0 1
1 0
1
1
仔细观察三角形第偶数个的小三角形（无法跟上，左上，右上）组成新三角形。
从上往下遍历：j=[1,3,5,7]
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j+1])+1
0
1 0 0 1 1 1 1 0
1 1 1 1 2 0 1
2 1 2 0 1
3 0
1
1
同样第奇数个的小三角形（无法跟下，左下，右下）组成新三角形。
从下往上遍历：j=[2,4,6,8]
dp[i][j]=min(dp[i+1][j-1],dp[i+1][j+1])+1
0
1 0 0 1 1 1 1 0
1 1 1 1 2 0 1
2 1 2 0 1
3 0
1
1
输出：max(dp[i][j])^2
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #define MAXN 205 5 using namespace std; 6 7 int n; 8 int dp[MAXN][MAXN]; 9 10 int main() 11 { 12 while( scanf("%d",&n)!=EOF && n ){ 13 memset(dp,0,sizeof(dp)); 14 int k=0; 15 char ch; 16 for(int i=1; i<=n; i++){ 17 getchar(); 18 for(int j=1; j<=((n-i+1)*2-1)+k; j++){ 19 scanf("%c",&ch); 20 if(ch==‘ ‘ || ch==‘#‘){ 21 dp[i][j]=0; 22 } 23 if(ch==‘-‘){ 24 dp[i][j]=1; 25 } 26 } 27 k++; 28 } 29 for(int i=1; i<=n; i++){ 30 for(int j=i; j<=2*n-i; j+=2){ 31 if(dp[i][j] && dp[i-1][j]){ 32 dp[i][j]=min( dp[i-1][j-1] , dp[i-1][j+1] )+1; 33 } 34 } 35 } 36 for(int i=n-1; i>=1; i--){ 37 for(int j=i+1; j<=2*n-i; j+=2){ 38 if(dp[i][j] && dp[i+1][j]){ 39 dp[i][j]=min( dp[i+1][j-1] , dp[i+1][j+1] )+1; 40 } 41 } 42 } 43 int ans=-1; 44 for(int i=1; i<=n; i++){ 45 for(int j=i; j<=2*n-i; j++){ 46 if(dp[i][j]>ans){ 47 ans=dp[i][j]; 48 } 49 } 50 } 51 printf("Triangle #%d\n",++c); 52 printf("The largest triangle area is %d.\n",ans*ans); 53 puts(""); 54 } 55 return 0; 56 }
原文：http://www.cnblogs.com/chenjianxiang/p/3562343.html