ACM学习-POJ-1088-滑雪

本是古典何须时尚 2022-09-07 14:40 179阅读 0赞

**菜鸟学习ACM，纪录自己成长过程中的点滴。**

**学习的路上，与君共勉。**

**ACM学习-POJ-1088-滑雪**

<table style="font-family:Times"> 
 <tbody> 
  <tr> 
   <td> 
    <div style="text-align:center; font-size:18pt; font-weight:bold; color:blue">
      滑雪 
    </div> 
    <div style="text-align:center; font-size:12pt"> 
     <table> 
      <tbody> 
       <tr> 
        <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
        <td>&nbsp;</td> 
        <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
       </tr> 
       <tr> 
        <td><strong>Total Submissions:</strong>&nbsp;69092</td> 
        <td>&nbsp;</td> 
        <td><strong>Accepted:</strong>&nbsp;25490</td> 
       </tr> 
      </tbody> 
     </table> 
    </div> <p style="text-align:left; font-size:18pt; font-weight:bold; color:blue"> Description</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt">
      Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子&nbsp; 
     <br> 
     <pre> 1  2  3  4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9</pre> 
     <br> 一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。 
    </div> <p style="text-align:left; font-size:18pt; font-weight:bold; color:blue"> Input</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt">
      输入的第一行表示区域的行数R和列数C(1 &lt;= R,C &lt;= 100)。下面是R行，每行有C个整数，代表高度h，0&lt;=h&lt;=10000。 
    </div> <p style="text-align:left; font-size:18pt; font-weight:bold; color:blue"> Output</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt">
      输出最长区域的长度。 
    </div> <p style="text-align:left; font-size:18pt; font-weight:bold; color:blue"> Sample Input</p> <pre style="font-family:'Courier New',Courier,monospace; font-size:12pt">5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
</pre> <p style="text-align:left; font-size:18pt; font-weight:bold; color:blue"> Sample Output</p> <pre style="font-family:'Courier New',Courier,monospace; font-size:12pt">25</pre> <p style="text-align:left; font-size:18pt; font-weight:bold; color:blue"> Source</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt"> 
     <a href="http://poj.org/searchproblem?field=source&amp;key=SHTSC+2002" style="text-decoration:none" rel="nofollow">SHTSC 2002</a> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

**题目要求:**

**...全中文题目，就不多做废话了。**

**题目分析:**

**典型的动态规划题目，采用记忆化搜索，利用一个数组保存每个点的最大值，(动态规划的优点，避免重复计算子问题) 对每个点 进行上下左右 的求解，该点 的最大值 肯定是 从 四个方向 中最大 的 +1。 按照这个思想，不然求解。**

下面给出AC代码。

#include <stdio.h>
    #include <math.h>
    #define MAX_NUM 101
    
    int map_arr[MAX_NUM][MAX_NUM]; //保存各个点高度
    int dp_arr[MAX_NUM][MAX_NUM];  //保存各个点的最大值
    
    int dp_x[] = {-1, 0, 1, 0}; //四个方向
    int dp_y[] = {0, -1, 0, 1};
    
    //返回2个数中的最大值
    int find_max( int num1, int num2 )
    {
        if (num1 > num2)
            return num1;
        else
            return num2;
    }
    int search_max( int x, int y )
    {
        int i;
        int xx_, yy_;
        if (dp_arr[x][y])  //如果不是0，即已经找到该点的最大值，直接返回，避免重复计算
            return dp_arr[x][y];
        for (i=0; i<4; i++)   //找出四个方向中满足条件的最大值。
        {
            xx_ = x + dp_x[i];
            yy_ = y + dp_y[i];
            
            if (map_arr[xx_][yy_] != -1 &&  map_arr[xx_][yy_] < map_arr[x][y])
            {
                dp_arr[x][y] = find_max(dp_arr[x][y], search_max(xx_, yy_)+1);
            }
        }
        
        return dp_arr[x][y];
        
    }
    
    int main()
    {
        int row, column;
        int i, j;
        int max_;
        
        while (scanf("%d %d", &row, &column) == 2)  //取得行列数
        {
            for (i=0; i<MAX_NUM; i++ ) //初始化各个点高度,默认-1，表示不存在。
            {
                for (j=0; j<MAX_NUM; j++)
                {
                    map_arr[i][j] = -1;
                    
                }
            }
            for (i=1; i<=row; i++)
            {
                for (j=1; j<=column; j++)
                {
                    scanf("%d", &map_arr[i][j]); //输入各个点的高度
                    dp_arr[i][j] = 0;
                }
            }
            
            max_ = 0;
            
            for (i=1; i<=row; i++)
            {
                for (j=1; j<=column; j++)
                {
                    max_ = find_max(max_, search_max(i, j)); //找出最大值
                }
            }
            
            printf("%d\n", max_ + 1 ); //＋1.  因为最后一个点没被算进去。
        }
        
        return 0;
    }