首页 > 其他分享 >滑雪 OJ3651

滑雪 OJ3651

时间:2023-05-24 12:55:06浏览次数:43  
标签:滑雪 int dfs y1 x1 OJ3651 dp

这个题我是不会用dp做,众所周知,能用记忆化搜索的题肯定能用dp,能用dp的不一定用记忆化搜索.

这个题正好用记忆化搜索可以过,欸嘿

#include<bits/stdc++.h>
using namespace std;
const int N=2020;
int f[N][N],a[N][N],n,m,res;//a数组存储状态,f数组存储每条路最大的值
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int dfs(int x,int y)
{
    if(f[x][y]) return f[x][y];//如果本来就存在,那就直接返回
    for(int i=0;i<4;i++)
    {
        int x1=x+dx[i],y1=y+dy[i];
        if(x1<=0||y1<=0||x1>n||y1>m) continue;//切记判断(呜呜)
        if(a[x][y]>a[x1][y1])
            f[x][y]=max(f[x][y],dfs(x1,y1)+1);//看看走x1,y1这条路和现在的路哪个长;
    }
    return f[x][y];//返回
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) cin>>a[i][j];
    for(int i=1;i<=n;i++)    
    {
        for(int j=1;j<=m;j++)
            res=max(res,dfs(i,j));//每条都要搜一下,因为是记忆化搜索,所以有地方已经搜过了,不用担心复杂度
    }
    cout<<res+1;
    return 0;
}

 

标签:滑雪,int,dfs,y1,x1,OJ3651,dp
From: https://www.cnblogs.com/o-Sakurajimamai-o/p/17427972.html

相关文章

  • AcWing901. 滑雪(python)
    题目详情知识点记忆化DP思路自己的思路(仅参考):一开始想的是找最大值,然后从最大值开始向下滑,但是我们是要求最长路径,不一定是从最高的点滑下去的,也不一定是滑到最低点,而且会存在最大值不止一个的情况,所以我们应该是针对每一个点,都求出当前该点出发能去的最长路径,然后求完之后......
  • 2023年中国传媒大学程序设计大赛 G.跳台滑雪 线段树
    传送门#include<iostream>#include<cstring>#include<iomanip>#include<algorithm>#include<stack>#include<queue>#include<numeric>#include<cassert>#......
  • POJ 1088 滑雪 递归+dp | 拓扑排序
    从每个点(i,j)向四个方向去看如果某一个方向(a,b)的数值比当前位置小先求解(a,b)的最长距离,之后加1即可朴素的递归重复求解了很多子问题,我们每计算出一个子问题的解,便......
  • B - 滑雪【2022GDUT寒假集训-简单DP】
    B-滑雪原题链接思路\(定义f(i,j)为从坐标(i,j)出发的最大值\)\(状态转移方程f(i,j)=max(f(i+dx[k],j+dy[k]))\)\(答案为max(f(1,1),f(1,2),...,f(n,m))\)注意......
  • 洛谷 P1434 [SHOI2002] 滑雪
    P1434[SHOI2002]滑雪-洛谷|计算机科学教育新生态(luogu.com.cn)这道题数据很水,可以用记忆化过,这里说一下堆优化+DP的方法 首先是常用的DP逆向思维,也是此题最终......
  • 洛谷 P1434 [SHOI2002] 滑雪 首次markdown测试
    [SHOI2002]滑雪题目描述Michael喜欢滑雪。这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来......
  • 犁式滑雪要领
       犁式直滑降:屈膝约下蹲45度,板尖维持一个拳头的距离,控制两个板尾之间的距离,扩大距离时是减速,缩小距离时是加速。犁式刹车刹车时,两个板之间距离越大,刹车效果也明显,......
  • NC20568 [SCOI2012]滑雪与时间胶囊
    题目链接题目题目描述a180285非常喜欢滑雪。他来到一座雪山,这里分布着M条供滑行的轨道和N个轨道之间的交点(同时也是景点),而且每个景点都有一编号i(1≤i≤N)和一高度Hi......
  • 上架亚马逊的自行车、滑雪和滑板头盔的标准是什么
    自行车头盔、滑雪头盔和滑板头盔上架亚马逊的有哪些规定标准?      头盔是作为个人防护类产品的最重要的一部分,肩负着保护运动人士生命安全的重任。越来越多的运动需......
  • P1434 [SHOI2002] 滑雪(记忆化搜索 DAG)
    P1434[SHOI2002]滑雪题意给你一个\(n\timesm\)的矩阵\(A\),\(A_{i,j}\)代表\((i,j)\)这个地方的高度,你可以从任意一个地方出发,然后走到一个和这个地方四联通......