http://acm.pku.edu.cn/JudgeOnline/problem?id=1088
非常经典的一道动态规划题，AC的时候心情简直舒畅到了极点．
时间限制是1000MS，如果直接用DFS肯定超时的．
马上想到动归，
用opt[i][j]记录从点node[i][j]出发的最短路径（不算本身，只算延伸；也就是初始值为0）
状态转移方程opt[i][j]=max{ opt[i+1][j],opt[i-1][j],opt[i][j+1],opt[i][j-1] } +１
也就是说，opt[i][j]的值等于从node[i][j]的上下左右四个方向出发所滑的最长值＋１；
而这道题并不是简单的动归，计算opt[i][j]的过程需要类似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]; //放置每个坐标上的高度
5int opt[101][101]; //放置从每个坐标出发的最优解
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]; //如果已经计算出,直接返回
18 for(k=0;k<4;k++) //向四个方向延伸
19
{
20 if(ok(i+dx[k],j+dy[k])) //如果节点没有超出边界
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); //输出值需要＋１ ，因为在前面的计算中，每个点的初始值都是0
53
54 return ;
55}
56