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] } +1
也就是说,opt[i][j]的值等于从node[i][j]的上下左右四个方向出发所滑的最长值+1;
而这道题并不是简单的动归,计算opt[i][j]的过程需要类似DFS的递归方法.这就是记忆化搜索.
Problem Id:1088 User Id:lnmm
Memory:152K Time:0MS
Language:C++ Result:Accepted
1
#include"stdio.h"
2![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
const int dx[]=
{-1,0,1,0},dy[]=
{0,1,0,-1};
3
int r,c;//r和c分别是行和列
4
int node[101][101]; //放置每个坐标上的高度
5
int opt[101][101]; //放置从每个坐标出发的最优解
6![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
7
bool ok(int i,int j)
8![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
9
return (i>=1 && i<=r && j>=1 &&j<=c);
10
}
11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
12![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
13![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
14
int dp(int i,int j)
15![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
16
int k;
17
if(opt[i][j]>0) return opt[i][j]; //如果已经计算出,直接返回
18
for(k=0;k<4;k++) //向四个方向延伸
19![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
20
if(ok(i+dx[k],j+dy[k])) //如果节点没有超出边界
21
if( node[i+dx[k]][j+dy[k]]<node[i][j] ) //满足滑雪条件
22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
29![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
33
34![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
35
}
36![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
37
void main()
38![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
39
int max=0,i,j;
40
scanf("%d%d",&r,&c);
41![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
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); //输出值需要+1 ,因为在前面的计算中,每个点的初始值都是0
53![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
54
return ;
55
}
56![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)