pku1088 滑雪

 

#include<stdio.h>
#include<string.h>

const int dir[][2]={{-1,0},{0,-1},{1,0},{0,1}};
const int Maxn=100;

int g[Maxn][Maxn],num[Maxn][Maxn];
int n,m;

int dp(int x,int y)
{
    if(num[x][y]!=0)        
    {
        return num[x][y];
    }

    for(int move=0;move<4;move++)            
    {
        int newx=x+dir[move][0];
        int newy=y+dir[move][1];
        if(newx<0||newx>=n||newy<0||newy>=m)
            continue;
        if(g[newx][newy]<g[x][y])
        {
            int temp=dp(newx,newy)+1;
            if(temp>num[x][y])
                num[x][y]=temp;
        }
    }

    return num[x][y];  //注明：在一个搜索中的最后一次递归查找只执行了该句返回初始化值0
}

int main()
{
    scanf("%d%d",&n,&m);

    int i,j;
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
        {
            scanf("%d",g[i]+j);
        }

    memset(num,0,sizeof(num));

    int max=0;
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
        {
            int temp=dp(i,j);
            if(max<temp)
                max=temp;
        }
    printf("%d\n",max+1);
    return 0;
}


 

解题思路：

采用记忆化搜索，即DFS+DP.