第13讲动态规划

课件：（下载）

【POJ1088】滑雪

#include <iostream>
using namespace std;
#define MAX 100

int map[MAX][MAX];
int temp[MAX][MAX];
int r,c;

void Init()
{
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            cin>>map[i][j];
        }
    }
    memset(temp,0,sizeof(temp));
}

int Step(int x,int y)
{
    if(temp[x][y]>0)
        return temp[x][y];

    int max = 0;
    if(x>0)
        if( map[x][y]>map[x-1][y] )
            if( max < Step(x-1,y) )
                max = Step(x-1,y);
    if(x<r-1)
        if( map[x][y]>map[x+1][y] )
            if( max < Step(x+1,y) )
                max = Step(x+1,y);
    if(y>0)
        if( map[x][y]>map[x][y-1] )
            if( max < Step(x,y-1) )
                max = Step(x,y-1);
    if(y<c-1)
        if( map[x][y]>map[x][y+1] )
            if( max < Step(x,y+1) )
                max = Step(x,y+1);
    temp[x][y] = max + 1;

    return temp[x][y];
}

int Search()
{
    int max=0;
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            Step(i,j);
            if( max < temp[i][j] )
                max = temp[i][j];
        }
    }
    return max;
}

int main()
{
    while(cin>>r>>c)
    {
        Init();
        cout<<Search()<<endl;
    }
    return 0;
}