poj 1088スキー
9229 ワード
古典的な動的計画の問題:
1 #include<iostream>
2
3 using namespace std;
4
5 int b[101][101];
6 int d[101][101];
7 int r,c;
8
9
10 int dp(int i,int j)
11 {
12 int max=0;
13
14 if(d[i][j]!=0)
15 return d[i][j];
16
17 //
18 if(i-1>=0)
19 {
20 if(b[i-1][j]<b[i][j])
21 {
22 int temp=dp(i-1,j);
23 if(max<temp) max=temp;
24 }
25 }
26
27 if(i+1<r)
28 {
29 if(b[i+1][j]<b[i][j])
30 {
31 int temp=dp(i+1,j);
32 if(max<temp) max=temp;
33 }
34 }
35
36 if(j-1>=0)
37 {
38 if(b[i][j-1]<b[i][j])
39 {
40 int temp=dp(i,j-1);
41 if(max<temp) max=temp;
42 }
43 }
44
45 if(j+1<c)
46 {
47 if(b[i][j+1]<b[i][j])
48 {
49 int temp=dp(i,j+1);
50 if(max<temp) max=temp;
51 }
52 }
53
54 return d[i][j]=max+1;
55 }
56
57 int main()
58 {
59 int i,j;
60 cin>>r>>c;
61 for(i=0;i<r;++i)
62 for(j=0;j<c;++j)
63 cin>>b[i][j];
64 memset(d,0,sizeof(d));
65 for(i=0;i<r;++i)
66 for(j=0;j<c;++j)
67 dp(i,j);
68 int max=0;
69 for(i=0;i<r;++i)
70 for(j=0;j<c;++j)
71 if(d[i][j]>max) max=d[i][j];
72 cout<<max<<endl;
73 return 0;
74
75 }