Acwing.901 滑雪(动态规划)

这篇具有很好参考价值的文章主要介绍了Acwing.901 滑雪(动态规划)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

给定一个R行C列的矩阵,表示一个矩形网格滑雪场。
矩阵中第i行第j列的点表示滑雪场的第i行第j列区域的高度。
一个人从滑雪场中的某个区域内出发,每次可以向上下左右任意一个方向滑动一个单位距离。当然,一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。下面给出一个矩阵作为例子:

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-2-1。
在给定矩阵中,最长的滑行轨迹为25-24-23-…-3-2-1,沿途共经过25个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度,请你找出在该滑雪场中能够完成的最长滑雪轨迹,并输出其长度(可经过最大区域数)。

输入格式

第一行包含两个整数R和C。
接下来R行,每行包含C个整数,表示完整的二维矩阵。

输出格式

输出一个整数,表示可完成的最长滑雪长度。

数据范围

1≤R,C ≤300,
0≤矩阵中整数≤10000

  • 输入样例:
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
  • 输出样例:
25

代码

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author akuya
 * @create 2023-07-28-23:26
 */
public class skiing {
    static int N=310;
    static int n,m;
    static int h[][]=new int[N][N];
    static int f[][]=new int[N][N];
    static int dx[]={-1,0,1,0};
    static int dy[]={0,1,0,-1};

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        m= scanner.nextInt();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                h[i][j]=scanner.nextInt();

        for(int i=0;i<N;i++)
            Arrays.fill(f[i],-1);

        int res=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                res=Math.max(res,dp(i,j));

        System.out.println(res);
    }

    public static int dp(int x,int y){
        if(f[x][y]!=-1)return f[x][y];
        f[x][y]=1;
        for(int i=0;i<4;i++){
            int a=x+dx[i];
            int b=y+dy[i];
            if(a>=1&&a<=n&&b>=1&&b<=m&&h[a][b]<h[x][y])
                f[x][y]=Math.max(f[x][y],dp(a,b)+1);
        }

        return f[x][y];
    }
}

思路

本题是运用到记忆化搜索的动态规划,具体分析如下图
Acwing.901 滑雪(动态规划),java算法实录,动态规划,算法
这里的代码用到了递归,运用递归思路代码很好实现,就是在某些数据范围下可能爆栈。这道题当然没有问题,大家视情况使用。文章来源地址https://www.toymoban.com/news/detail-616025.html

到了这里,关于Acwing.901 滑雪(动态规划)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法|动态规划 | 01背包问题No.2】AcWing 423. 采药

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成

    2024年02月06日
    浏览(50)
  • 【AcWing算法基础课】第五章 动态规划(未完待续)

    本专栏文章为本人AcWing算法基础课的学习笔记,课程地址在这。如有侵权,立即删除。 dp问题的优化 :在基本形式dp上作等价变形。 dp问题的解题方法 : 1)状态表示 集合 属性:最大值/最小值/数量。 2)状态计算 集合划分(不重不漏) 题目链接: 2. 01背包问题 - AcWing题库

    2024年02月12日
    浏览(73)
  • acwing算法基础之动态规划--线性DP和区间DP

    线性DP:状态转移表达式存在明显的线性关系。 区间DP:与顺序有关,状态与区间有关。 题目1 :数字三角形。 解题思路:直接DP即可, f[i][j] 可以来自 f[i-1][j] + a[i][j] 和 f[i-1][j-1] + a[i][j] ,注意 f[i-1][j] 不存在的情况(最后一个点)和 f[i-1][j-1] 不存在的情况(第一个点)。

    2024年02月04日
    浏览(52)
  • acwing算法基础之动态规划--数位统计DP、状态压缩DP、树形DP和记忆化搜索

    暂无。。。 暂无。。。 题目1 :求a~b中数字0、数字1、…、数字9出现的次数。 思路:先计算1~a中每位数字出现的次数,然后计算1~b-1中每位数字出现的次数,两个相减即是最终答案。 那么,如何计算1~a中每位数字出现的次数呢? 首先,将a的每一位存入向量num中,例如a=123

    2024年02月04日
    浏览(51)
  • AcWing算法学习笔记:动态规划(背包 + 线性dp + 区间dp + 计数dp + 状态压缩dp + 树形dp + 记忆化搜索)

    算法 复杂度 时间复杂度0(nm) 空间复杂度0(nv) 代码 算法 通过滚动数组对01背包朴素版进行空间上的优化 f[i] 与 f[i - 1]轮流交替 若体积从小到大进行遍历,当更新f[i, j]时,f[i - 1, j - vi] 已经在更新f[i, j - vi]时被更新了 因此体积需要从大到小进行遍历,当更新f[i, j]时,f[i - 1,

    2024年02月21日
    浏览(43)
  • Acwing.285 没有上司的舞会(动态规划)

    Ural大学有N名职员,编号为1~N。 他们的关系就像—棵以校长为根的树,父节点就是子节点的直接上司。每个职员有一个快乐指数,用整数H给出,其中1≤i≤N。 现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。 在满足这个条件的前提下,主办方希望邀请

    2024年02月15日
    浏览(74)
  • Acwing.291 蒙德里安的梦想(动态规划)

    求把N M的棋盘分割成若干个1 2的的长方形,有多少种方案。 例如当N=2,M=4时,共有5种方案。当N=2,M=3时,共有3种方案。如下图所示: 输入包含多组测试用例。 每组测试用例占一行,包含两个整数N和M。 当输入用例N=0,M=0时,表示输入终止,且该用例无需处理。 每个测试用例

    2024年02月15日
    浏览(38)
  • Acwing.91 最短Hamilton路径(动态规划)

    给定一张n个点的带权无向图,点从0~n-1标号,求起点0到终点n-1的最短Hamilton路径。Hamilton路径的定义是从0到n-1不重不漏地经过每个点恰好一次。 第—行输入整数n。 接下来n行每行n个整数,其中第i行第j个整数表示点i到j的距离(记为a[i.i])。对于任意的, y,z,数据保证a[x,x]=0,

    2024年02月15日
    浏览(43)
  • AcWing 1.2.1 最长上升子序列模型 + 动态规划 + 图解(详细)

    (1)acwing 4557. 最长上升子序列  4557. 最长上升子序列 - AcWing题库 给定一个长度为 N 的整数序列  a1,a2,…,aN 。请你计算该序列的 最长上升子序列的长度 。上升子序列是指数值 严格单调递增的子序列 输入格式 第一行包含整数 N 第二行包含 N个整数 a1,a2,…,aN 输出格式 一行

    2024年02月06日
    浏览(40)
  • 算法-动态规划-java

    动态规划的核心 哪些不记得过去的人,都注定要重蹈覆辙 (因为要记录过去的事情,所以是典型的空间换时间) 动态规划算法的两种形式 上面已经知道动态规划算法的核心是记住已经求过的解,记住求解的方式有两种: ①自顶向下的备忘录法 ②自底向上。 举一个最简单的

    2024年02月07日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包