http://acm.pku.edu.cn/JudgeOnline/problem?id=1088
非常經(jīng)典的一道動(dòng)態(tài)規(guī)劃題，AC的時(shí)候心情簡(jiǎn)直舒暢到了極點(diǎn)．
時(shí)間限制是1000MS，如果直接用DFS肯定超時(shí)的．
馬上想到動(dòng)歸，
用opt[i][j]記錄從點(diǎn)node[i][j]出發(fā)的最短路徑（不算本身，只算延伸；也就是初始值為0）
狀態(tài)轉(zhuǎn)移方程opt[i][j]=max{ opt[i+1][j],opt[i-1][j],opt[i][j+1],opt[i][j-1] } +１
也就是說(shuō)，opt[i][j]的值等于從node[i][j]的上下左右四個(gè)方向出發(fā)所滑的最長(zhǎng)值＋１；
而這道題并不是簡(jiǎn)單的動(dòng)歸，計(jì)算opt[i][j]的過(guò)程需要類似DFS的遞歸方法．這就是記憶化搜索．
Problem Id:1088 User Id:lnmm
Memory:152K Time:0MS
Language:C++ Result:Accepted
1
#include"stdio.h"
2
const int dx[]=
{-1,0,1,0},dy[]={0,1,0,-1};
3int r,c;//r和c分別是行和列
4int node[101][101]; //放置每個(gè)坐標(biāo)上的高度
5int opt[101][101]; //放置從每個(gè)坐標(biāo)出發(fā)的最優(yōu)解
6
7bool ok(int i,int j)
8{
9
return (i>=1 && i<=r && j>=1 &&j<=c);
10
}
11
12
13
14int dp(int i,int j)
15{
16 int k;
17 if(opt[i][j]>0) return opt[i][j]; //如果已經(jīng)計(jì)算出,直接返回
18 for(k=0;k<4;k++) //向四個(gè)方向延伸
19
{
20 if(ok(i+dx[k],j+dy[k])) //如果節(jié)點(diǎn)沒(méi)有超出邊界
21 if( node[i+dx[k]][j+dy[k]]<node[i][j] ) //滿足滑雪條件
22 {
23 if( opt[i][j]< dp(i+dx[k],j+dy[k])+1 )
24 opt[i][j]=dp(i+dx[k],j+dy[k])+1;
25
}
26 }
27 return opt[i][j];
28
29
30// if(ok(i+dx[k],j+dy[k])&&node[i+dx[k]][j+dy[k]]<node[i][j]&&opt[i][j]>dp(i+dx[k],j+dy[k])+1)
31// opt[i][j]=dp(i+dx[k],j+dy[k])+1;
32
33
34
35}
36
37void main()
38{
39 int max=0,i,j;
40 scanf("%d%d",&r,&c);
41
42 for(i=1;i<=r;i++)
43 for(j=1;j<=c;j++)
44 scanf("%d",&node[i][j]);
45 for(i=1;i<=r;i++)
46 for(j=1;j<=c;j++)
47 opt[i][j]=0;
48
49 for(i=1;i<=r;i++)
50 for(j=1;j<=c;j++)
51 if(max<dp(i,j))max=dp(i,j);
52 printf("%d",max+1); //輸出值需要＋１ ，因?yàn)樵谇懊娴挠?jì)算中，每個(gè)點(diǎn)的初始值都是0
53
54 return ;
55}
56