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

int v[110][110];
int dp[110][110];

int cmax(int a,int  b,int c,int d)
{
    if(a >= b && a >= c && a >= d)  return a;
    if(b >= a && b >= c && b >= d)  return b;
    if(c >= a && c >= b && c >= d)  return c;
    if(d >= b && d >= c && d >= a)  return d;
    return -1;
}

int d(int i,int j)
{
    int up = -1,dn = -1,le = -1,rt = -1;
    if(dp[i][j] >= 0)   return dp[i][j];
    if(v[i][j] > v[i - 1][j])   up = d(i - 1,j);
    if(v[i][j] > v[i + 1][j])   dn = d(i + 1,j);
    if(v[i][j] > v[i][j - 1])   le = d(i,j - 1);
    if(v[i][j] > v[i][j + 1])   rt = d(i,j + 1);
    if(up == -1 && dn == -1 && le == -1 && rt == -1)
        return dp[i][j] = 1;
    else
        return dp[i][j] = 1 + cmax(up,dn,le,rt);
}

int main()
{
    int r,c,i,j,smax;
    while(scanf("%d%d",&r,&c) != EOF)
    {
        memset(dp,-1,sizeof(dp));
        memset(v,MAX,sizeof(v));
        smax = -1;
        for(i = 1;i <= r;i++)
            for(j = 1;j <= c;j++)   scanf("%d",&v[i][j]);
        for(i = 1;i <= r;i++)
            for(j = 1;j <= c;j++)
            {
                dp[i][j] = d(i,j);
                if(smax < dp[i][j])  smax = dp[i][j];
            }
        printf("%d\n",smax);
    }
    return 0;
}

• Re:经典DP，贴代码，飘过~~ (1412) 200931000814 2011-03-28 19:11:16