首页 > 代码库 > poj 1088

poj 1088

hnldyhy(303882171) 11:28:19
poj 1088
//DP

#include <iostream>
using namespace std;

int a[102][102],b[102][102];
int r, c,ans;
int f( int i, int j )
{ int max=1,t;
if( b[i][j] > 1 ) return b[i][j];
if( i + 1 <= r && a[i][j] > a[i+1][j] )
{ t = f( i + 1, j ) + 1;
if( max < t ) max = t;
}
if( j + 1 <= c && a[i][j] > a[i][j+1] )
{ t = f( i, j + 1 ) + 1;
if( max < t ) max = t;
}
if( i - 1 > 0 && a[i][j] > a[i-1][j] )
{ t = f( i - 1, j ) + 1;
if( max < t ) max = t;
}
if( j - 1 > 0 && a[i][j] > a[i][j-1] )
{ t = f( i, j - 1 ) + 1;
if( max < t) max = t;
}
return max;
}

int main()
{ int i,j;
cin >> r >> c;
for ( i = 1; i <= r; ++i )
for ( j = 1; j <= c; ++j )
{ cin >> a[i][j]; b[i][j] = 1; }
ans = 1;
for( i = 1; i <= r; ++i )
for( j = 1; j <= c; ++j )
{ b[i][j] = f( i, j );
if( ans < b[i][j] ) ans = b[i][j];
}
cout << ans <<endl;
}