动态规划(DP)，模拟

题目链接：http://poj.org/problem?id=1088

Memory: 252KTime: 16MSLanguage: C++Result: Accepted

解题报告：

1、lm[i][j]表示maps[i][j]所能到达的最长长度

2、状态转移方程

    lm[i][j]=max(maps[i][j]四周的最大lm)+1;

 

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

using namespace std;

#define MAX 105

int row,col;
int maps[MAX][MAX];///图表
int lm[MAX][MAX];///lm[i][j]表示maps[i][j]所能到达的最长长度
int mov[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

int DP(int i,int j)///求maps[i][j]所能到达的最长长度
{
    if(lm[i][j]!=0)
        return lm[i][j];
    else
    {
        int maxx=0,s;
        for(int k=0;k<4;k++)
        {
            int tx=i+mov[k][0];
            int ty=j+mov[k][1];
            if(tx>=0&&tx<row&&ty>=0&&ty<col)
            {
                if(maps[i][j]>maps[tx][ty])
                {
                    s=DP(tx,ty);
                    if(s>maxx)
                        maxx=s;
                }
            }
        }
        lm[i][j]=maxx+1;
        return maxx+1;
    }
}
int main()
{
    int MAXLEN=0;
    scanf("%d%d",&row,&col);
    for(int i=0;i<row;i++)
    {
        for(int j=0;j<col;j++)
            scanf("%d",&maps[i][j]);
    }
    memset(lm,0,sizeof(lm));
    for(int i=0;i<row;i++)
    {
        for(int j=0;j<col;j++)
        {
            lm[i][j]=DP(i,j);
            if(MAXLEN<lm[i][j])
                MAXLEN=lm[i][j];
        }
    }
    printf("%d\n",MAXLEN);
    return 0;
}