Posted on 2008-08-21 10:58
Hero 閱讀(167)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //1088 Accepted 440K 16MS C++ 1725B
2
3 //DP--排序后DP
4 //dp[i][j] = fmax( dp[i][j], dp[m][n]+1 ) ;
5 //[m][n]是和[i][j]相鄰的且val比[i][j]小的坐標
6
7 #include <stdio.h>
8 #include <stdlib.h>
9 #include <string.h>
10
11 const int size = 120 ;
12 int data[size][size] ;
13 int dp[size][size] ;
14 struct NODE
15 {
16 int row ;
17 int col ;
18 int val ;
19 };
20 struct NODE node[size*size] ;
21 int cnode = 0 ;
22 int row, col ;
23
24 int fmax( int a, int b )
25 {
26 return a > b ? a : b ;
27 }
28
29 void input()
30 {
31 memset( data, -1, sizeof(data) ) ; cnode = 0 ;
32 for( int i=1; i<=row; i++ ) for( int j=1; j<=col; j++ ) {
33 scanf( "%d", &data[i][j] ) ;
34 node[cnode].row = i ; node[cnode].col = j ; node[cnode++].val = data[i][j] ;
35 }
36 }
37
38 int cmp( const void *a, const void *b )
39 {
40 struct NODE *c = (struct NODE *)a ;
41 struct NODE *d = (struct NODE *)b ;
42 return c->val - d->val ;
43 }
44
45 void process()
46 {
47 qsort( node, cnode, sizeof(node[0]), cmp ) ;//從小到大排序
48
49 memset( dp, 0, sizeof(dp) ) ;
50
51 int curc, curr ;
52 for( int i=0; i<cnode; i++ )
53 {
54 curr = node[i].row ; curc = node[i].col ; dp[curr][curc] = 1 ;//初始化
55 if( data[curr][curc] > data[curr][curc-1] )
56 dp[curr][curc] = fmax( dp[curr][curc], dp[curr][curc-1]+1 ) ;
57 if( data[curr][curc] > data[curr][curc+1] )
58 dp[curr][curc] = fmax( dp[curr][curc], dp[curr][curc+1]+1 ) ;
59 if( data[curr][curc] > data[curr-1][curc] )
60 dp[curr][curc] = fmax( dp[curr][curc], dp[curr-1][curc]+1 ) ;
61 if( data[curr][curc] > data[curr+1][curc] )
62 dp[curr][curc] = fmax( dp[curr][curc], dp[curr+1][curc]+1 ) ;
63 }
64 }
65
66 void output()
67 {
68 int maxlen = -1 ;
69 for( int i=1; i<=row; i++ ) for( int j=1; j<=col; j++ )
70 {
71 if( dp[i][j] > maxlen ) maxlen = dp[i][j] ;
72 }
73
74 printf( "%d\n", maxlen ) ;
75 }
76
77 int main()
78 {
79 while( scanf( "%d %d", &row, &col ) != EOF )
80 {
81 input() ;
82
83 process() ;
84
85 output() ;
86 }
87
88 return 0 ;
89 }