猫史档案馆

//顺治滑雪             //基本思路：
#include<bits/stdc++.h>//如果碰到dp数组不为零，直接返回dp。如果没搜过就遍历
using namespace std;   //把搜到的值给dp数组.
int a[510][510],dp[510][510],w[2][4]= {{1,-1,0,0},{0,0,1,-1}};
int m,n,ans;
bool panduan(int s1,int s2){ //判断是否合法
    if(s1>=1&&s1<=m&&s2>=1&&s2<=n)return true;
    return false;
}
int dfs(int x1,int x2){ //\|x1,x2表示现在在搜的那个位置
    if(dp[x1][x2]!=0)return dp[x1][x2];//记忆化
    int temp=0;
    for(int i=0;i<4;i++){ //各个方向搜索
        int xx=x1+w[0][i];
        int yy=x2+w[1][i];
        if(panduan(xx,yy)){
            if(a[xx][yy]<a[x1][x2]){ //如果能滑下去
                dp[xx][yy]=dfs(xx,yy);//搜索下一个
                temp=max(dp[xx][yy]+1,temp); //类似于动态规划的状态转移方程
                 
            }
        }
    }
    dp[x1][x2]=temp; 
    return dp[x1][x2];
}
int main() {
    memset(dp,0,sizeof(dp));
    ans=0;
    int i,j;
    cin>>m>>n;
    for(i=1;i<=m;i++){
        for(j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(i=1;i<=m;i++){
        for(j=1;j<=n;j++){
            dp[i][j]=dfs(i,j);
            ans=max(ans,dp[i][j]);//打擂台式比大小
        }
    } 
    cout<<ans+1;//加上本身
    return 0;
}

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

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

输入的第一行表示区域的行数R和列数C(1 < = R,C < = 500)。下面是R行，每行有C个整数，代表高度h，0< =h< =10000。

输出最长区域的长度。

样例输入 Copy

5 5

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

样例输出 Copy

具体解法已说明，下面我来说一下，记忆化搜索与搜索的区别是：记忆化搜索存储了每一个里问题的最优权值和，下次使用是直接调用即可。

这题一开始我先想到的是动态规划，结果发现细节不好处理。于是想到了枚举，结果写不出来。后来用模拟时间超限，用深搜还是时间超限。结果又做回动规了，写了个四重循环，因为起点是不确定的，结果我比正常的两重多了两个嵌套来确定起点，还是爆了。最后我想到可以把内两个循环写到函数里做一个记忆化搜索，也就是说，主函数里只要确定起点就行了。函数内部搜索过程与动规大同小异。int dfs(int x1,int x2){ //\|x1,x2表示现在在搜的那个位置

    if(dp[x1][x2]!=0)return dp[x1][x2];//记忆化
    int temp=0;
    for(int i=0;i<4;i++){ //各个方向搜索
        int xx=x1+w[0][i];
        int yy=x2+w[1][i];
        if(panduan(xx,yy)){
            if(a[xx][yy]<a[x1][x2]){ //如果能滑下去
                dp[xx][yy]=dfs(xx,yy);//搜索下一个
                temp=max(dp[xx][yy]+1,temp); //类似于动态规划的状态转移方程
                 
            }
        }
    }
    dp[x1][x2]=temp; 
    return dp[x1][x2];
}http://oj.xinzhiao.vip/problem.php?cid=1201&pid=2

猫史档案馆

【C++程序设计】记忆化搜索：滑雪问题

回复