UVa 10285 - Longest Run on a Snowboard(记忆化搜索)

昨天整理了博客目录,看紫书第九章还没有做的题,就翻书看到了这道水题。

给出r*c的数表代表每个地点的高度,滑雪时高度要严格降低,求最长滑雪路径。

记忆化搜索最长路径,将每个点的最长路径存在数组g中,算完一个点比较维护最长路径就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
const int maxn=110;
const int x[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int h[maxn][maxn],g[maxn][maxn];
int dp(int a,int b){
if(g[a][b]>=0) return g[a][b];//计算过的值直接使用。
bool flag=0;
for(int i=0;i<4;++i)
if(h[a][b]>h[a+x[i][0]][b+x[i][1]]&&h[a+x[i][0]][b+x[i][1]]!=-1){
g[a][b]=max(dp(a+x[i][0],b+x[i][1])+1,g[a][b]);//求当前点的最长滑雪路径。
flag=1;
}
if(!flag) return 0;//无法滑倒其他点路径长为0。
return g[a][b];
}
int main(){
int t;
scanf("%d",&t);
while(t--){
memset(h,-1,sizeof(h));
memset(g,-1,sizeof(g));
char s[maxn];
int r,c,best=0;
scanf("%s%d%d",s,&r,&c);
for(int i=1;i<=r;++i)
for(int j=1;j<=c;++j)
scanf("%d",&h[i][j]);
for(int i=1;i<=r;++i)
for(int j=1;j<=c;++j)
best=max(dp(i,j),best);//边计算边维护最长路径,省去一次遍历。
printf("%s: %d\n",s,best+1);
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。