題目是經典的DP入門，原來CTcoolL有一次拿來要做，當時還不知DP為何物，想要暴搜，現在又重新翻出來做一下
DP方程：len[ i ][ j ] = max{ len[ i-1][ j ], len[ i ][ j-1], len[ i+1][ j ], len[ i ][ j+1] };
代碼如下：
1
#include <iostream>
2using namespace std;
3
4int node[102][102];
5int len[102][102];
6int r, c;
7int getLength( int i, int j )
8{
9 if( len[i][j] > 0 )
10 return len[i][j];
11 int max = 0;
12 if( i + 1 <= r && node[i][j] > node[i+1][j] ){
13 int x = getLength( i + 1, j ) + 1;
14 if( max < x )
15 max = x;
16 }
17 if( j + 1 <= c && node[i][j] > node[i][j+1] ){
18 int x = getLength( i, j + 1 ) + 1;
19 if( max < x )
20 max = x;
21 }
22 if( i - 1 > 0 && node[i][j] > node[i-1][j] ){
23 int x = getLength( i - 1, j ) + 1;
24 if( max < x )
25 max = x;
26 }
27 if( j - 1 > 0 && node[i][j] > node[i][j-1] ){
28 int x = getLength( i, j - 1 ) + 1;
29 if( max < x)
30 max = x;
31 }
32 return max;
33
34}
35int main()
36{
37
38 cin >> r >> c;
39 for ( int i = 1; i <= r; ++i ){
40 for ( int j = 1; j <= c; ++j ){
41 cin >> node[i][j];
42 len[i][j] = 0;
43 }
44 }
45 int maxLen = 0;
46 for( int i = 1; i <= r; ++i ){
47 for( int j = 1; j <= c; ++j ){
48 len[i][j] = getLength( i, j );
49 if( maxLen < len[i][j] )
50 maxLen = len[i][j];
51 }
52 }
53 cout << maxLen + 1<<endl;
54 system( "pause" );
55}
56
posted on 2008-01-28 16:19
yoyouhappy 閱讀(2479)
評論(5) 編輯 收藏 引用 所屬分類:
yoyo的解題報告 、
acm/icpc