【dp】P1434 [SHOI2002]滑雪-白红宇

【dp】P1434 [SHOI2002]滑雪

阅读量：4333 次

发布时间：2019-06-07

本文共 3159 字，大约阅读时间需要 10 分钟。

题目描述

Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：

1   2   3   4   5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可行的滑坡为24－17－16－1（从24开始，在1结束）。当然25－24－23－...－3－2－1更长。事实上，这是最长的一条。

输入输出格式

输入格式：

输入的第一行为表示区域的二维数组的行数R和列数C（1≤R，C≤100）。下面是R行，每行有C个数，代表高度(两个数字之间用1个空格间隔)。

输出格式：

输出区域中最长滑坡的长度。

输入输出样例

输入样例#1：

5 51 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9

输出样例#1： 25

[思路]： 简单dp，虽然它在有技巧的搜索里面（其实dp好像和记忆化搜索差不多逃），然而怎么做呢？ dp[i][j]只能从四个方向走过来,而且四个方向的点的高度要大于这个点,于是就可以了.

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 using namespace std;const int maxn=999999999;const int minn=-999999999;inline int read(){ char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f;}int f[105][105];int a[105][105];int n,m,sum;int dp(int x,int y){ if (f[x][y]) return f[x][y]; int sum=0; if (x-1>0) if (a[x-1][y]>a[x][y]) sum=max(sum,dp(x-1,y)); if (x+1>0) if (a[x+1][y]>a[x][y]) sum=max(sum,dp(x+1,y)); if (y-1>0) if (a[x][y-1]>a[x][y]) sum=max(sum,dp(x,y-1)); if (y+1>0) if (a[x][y+1]>a[x][y]) sum=max(sum,dp(x,y+1)); f[x][y]=sum+1; return f[x][y];}int main(){ n=read(); m=read(); for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) { a[i][j]=read(); } for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) { if (f[i][j]==0) { f[i][j]=dp(i,j); } sum=max(sum,f[i][j]); } printf("%d",sum); return 0;}

然后我看了看题解，发现有记忆化搜索就厚颜无耻地粘过来了（嘿嘿）

by 更新时间: 2018-02-24 15:57

/*本题f数组表示当前坐标点滑下去的最大长度。状态转移方程：f[i][j]=max{f[i±1][j]+1,f[i][j±1}+1,f[i][j]}dfs函数采用逆推法。 */ #include
       
        #define maxn 110#define max(a,b)    a>b?a:busing namespace std;int map[maxn][maxn],f[maxn][maxn],r,c,dfs(int,int),m;/*map存跑道，f存答案，r，c为纵坐标横坐标，dfs搜索函数，两个变量分别为被搜索点的纵、横坐标。底下函数x，y打反了， 即x代表纵坐标，x代表横坐标，别看晕了m为最长跑道长度，全局变量初始值为0。 */ int main(){    scanf("%d%d",&r,&c);    for(int i=1;i<=r;i++)        for(int j=1;j<=c;j++){            scanf("%d",&map[i][j]);f[i][j]=1;/*    输入，因为自己滑到自己的长度是1，所以答案数组初始化为1。 */        }               for(int i=1;i<=r;i++)        for(int j=1;j<=c;j++)            m=max(m,dfs(i,j));      //进行搜索，如果结果比已知答案更大就更新。     printf("%d",m);                 //输出答案     return 0;}inline int dfs(int x,int y){        //搜索函数，其中x代表纵坐标，y代表横坐标，一开始打反了，后面懒得改了，别看晕了     if(f[x][y]!=1)  return f[x][y];    int b=0;/*    以下四句if，每个括号中前四句条件是否到达边界，最后一条件判断是否当前坐标比搜索坐标高。 */     if(x>=1&&y>=1&&x
        
         <=c&&map[x][y]>map[x+1][y])    b=max(b,(dfs(x+1,y)+1));    if(x>=1&&y>=1&&x<=r&&y
         
          map[x][y+1])    b=max(b,(dfs(x,y+1)+1));    if(x>1&&y>=1&&x<=r&&y<=c&&map[x][y]>map[x-1][y])    b=max(b,(dfs(x-1,y)+1));    if(x>=1&&y>1&&x<=r&&y<=c&&map[x][y]>map[x][y-1])    b=max(b,(dfs(x,y-1)+1));    f[x][y]=max(f[x][y],b); //防止4个if都不成立即b为0的情况。故取最大值     return f[x][y];}

转载于:https://www.cnblogs.com/pyyyyyy/p/10744270.html

你可能感兴趣的文章