PKU 1088滑雪解题报告

题 目分析：这个题目需要求出每个阶段的最大滑雪长度，状态转移的选择条件有两个：一：这个阶段的四个方向的数有比他本身小的，另一个条件：选择出满足条件一 的几个数中滑雪长度最大的那个。这样就完成了一次状态转移。这样不断递推下去就可以求出每个阶段的滑雪最大长度，然后遍历每个节点，找出最大的那个长度就 可以了。

提示：要用到记忆搜索，这样能避免重复递归。

源程序：

#include<iostream>

     using namespace std;

     int h[101][101];

     int sim[101][101];

     int r,c;

     int dp(int i,int j){

         int dir[2][4]={-1,0,1,0,0,1,0,-1};

         int m,max=0;//如果上下左右没有一个比自己小，这时候h[i][j]=max+1=1;这就是为什么要把max初始为0。

         if(h[i][j]!=0)

               return h[i][j];

         else{

               for(int k=0;k<4;k++){

                    if(i+dir[0][k]>=0&&i+dir[0][k]<r&&j+dir[1][k]>=0&&j+dir[1][k]<c)

                           if(sim[i][j]>sim[i+dir[0][k]][j+dir[1][k]]){

                                  m=dp(i+dir[0][k],j+dir[1][k]);

                                  if(max<m)//这个是用来在相邻的四个元素中（有时候没有四个）选择滑雪长度最大的　　　　　　路径作为h[i][j]的路径。

                                      max=m;     

                           }

                           else

                               continue;  

               }

              return max+1;//因为在这里max是上下左右几个元素的最大滑雪长度，而h[i][j]的值为包括了自己，所以要加上1。^_^注意这些相信你会AC了。

         }

     }

int soulve(){

    int max=0;

    for(int i=0;i<r;i++)

        for(int j=0;j<c;j++){

              h[i][j]=dp(i,j);

              if(max<h[i][j])

                    max=h[i][j];

        }    

    return max;         

}

int main(){

    while(cin>>r>>c){

         for(int i=0;i<r;i++)

             for(int j=0;j<c;j++){

                  cin>>sim[i][j];

                  h[i][j]=0;

             }

         cout<<soulve()<<endl;        

    }

}

总结：在这里值得注意的就是，记忆化搜索。在计算每个节点的滑雪最大值时要注意，用于比较上下左右的最大滑雪长度的语句应该紧跟递归其后。