UVa 10285 - Longest Run on a Snowboard（记忆化搜索）

发表于 分类于 ， Disqus：

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

给出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博客，格式可能有所偏差。 **

相关文章