首页 > ACM题库 > HDU-杭电 > HDU 1467 Triangles-动态规划-[解题报告] C++
2013
12-11

HDU 1467 Triangles-动态规划-[解题报告] C++

Triangles

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

5
#-##----#
 -----#-
  ---#-
   -#-
    -
4
#-#-#--
 #---#
  ##-
   -
0

样例输出:

Triangle #1
The largest triangle area is 9.

Triangle #2
The largest triangle area is 4.

dp题 有几点要注意

1.奇数偶数 分别对应两个方向

2.数组开得够大才行 要乘以2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#define maxn 2100
#define inf 2139062143
using namespace std;

int N;
char map[120*2][120*2];
int dp[120*2][120*2];
int ans;

int DP1()
{
    int i,j;
    int res=0;
    int kk=2*N-1;
    memset(dp,0,sizeof(dp));
    for(i=1; i<=kk; i=i+2)
    {
        if(map[1][i]=='-')
        {
            dp[1][i]=1;
            res=1;
        }
        else
        {
            dp[1][i]=0;
        }
    }

    for(i=2; i<=N; i++)
    {
        kk--;
        for(j=i; j<=kk; j=j+2)
        {
            if(map[i][j]=='-')
            {
                if(map[i-1][j]=='-')
                {
                    dp[i][j]=min(dp[i-1][j-1],dp[i-1][j+1])+1;
                }
                else
                {
                    dp[i][j]=1;
                }
            }
            else
            {
                dp[i][j]=0;
            }
            res=max(res,dp[i][j]);
        }
    }
    return res;
}

int DP2()
{
    int i,j;
    int res=0;
    int kk=N;
    for(i=N-1; i>=1; i--)
    {
        kk++;
        for(j=i+1; j<=kk; j=j+2)
        {
            if(map[i][j]=='-')
            {
                if(map[i+1][j]=='-')
                {
                    dp[i][j]=min(dp[i+1][j-1],dp[i+1][j+1])+1;
                }
                else
                {
                    dp[i][j]=1;
                }
            }
            else
            {
                dp[i][j]=0;
            }
            res=max(res,dp[i][j]);
        }
    }
    return res;
}

int main()
{
  //  freopen("input.txt","r",stdin);
    int i,j;
    int test=0;
    while(scanf("%d",&N)==1&&N)
    {
        getchar();
        for(i=1; i<=N; i++)
        {
            gets(map[i]+1);
            for(j=2*N-1+i; j<=2*N-1; j++)
            {
                map[i][j]=' ';
            }
            map[i][0]=' ';
        }
        ans=DP1();
        ans=max(ans,DP2());
        printf("Triangle #%d\n",++test);
        printf("The largest triangle area is %d.\n\n",ans*ans);
    }
    return 0;
}

 

解题报告转自:http://www.cnblogs.com/woaishizhan/archive/2013/04/07/3003447.html


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?