正文

p1434[shoi2002]滑雪dfs(代码片段)

bxd123  bxd123  2023-03-12  607

关键词：

题目描述

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 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

输出样例#1：复制

25

和之前做的周练水流很像
我可能用了效率最低的方法。。。强行dfs 32ms

#include<bits/stdc++.h>
using namespace std;
//input
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);i--)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m);
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define inf 0x3f3f3f3f
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define N 105
int dx[4]=0,0,1,-1;
int dy[4]=1,-1,0,0;
int n,m;
int mp[N][N];
bool inmap(int x,int y)

    return x>=1&&x<=n&&y>=1&&y<=m;

int maxx=-1;
int d[N][N];

void dfs(int x,int y,int cnt)

    if(cnt>=d[x][y])d[x][y]=cnt,maxx=max(maxx,cnt);
    else return  ;
    rep(i,0,3)
    
        int a=x+dx[i];
        int b=y+dy[i];
        if(!inmap(a,b))continue;
        if(mp[a][b]<=mp[x][y])continue;
        if(cnt+1<=d[a][b])continue;//如果步数更小或者相等 其实已经没有必要继续了

        dfs(a,b,cnt+1);
    
    return ;


int main()

    RII(n,m);
    rep(i,1,n)
    rep(j,1,m)
    RI(mp[i][j]),d[i][j]=1;
    rep(i,1,n)
    rep(j,1,m)
    if(d[i][j]==1)
    dfs(i,j,1);
    cout<<maxx;

View Code

p1434[shoi2002]滑雪记忆化搜索dp(代码片段)

https://www.luogu.com.cn/problem/P1434何为记忆化搜索，本质上就是我们已经知道每一个状态的值了，就无需重复的计算了，减少了时间的消耗。上图摘自：小呆呆大佬#include<bits/stdc++.h>usingnamespacestd;constintN=11... 查看详情

p1434[shoi2002]滑雪(代码片段)

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

[shoi2002]滑雪-题解报告(代码片段)

题目描述Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二... 查看详情

shoi2002滑雪(代码片段)

题面Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二维数... 查看详情

[shoi2002]滑雪（记忆化搜索模版）(代码片段)

题目链接：https://www.luogu.com.cn/problem/P1434 想法：记忆化搜索板子题：#include<algorithm>#include<string>#include<string.h>#include<vector>#include<map>#include<stack>#include<set>#include<queue>#include<math.h>#include&l... 查看详情

p1434滑雪

P1434滑雪题目描述Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域... 查看详情

p1434滑雪

洛谷p1434滑雪

洛谷——p1434滑雪

https://www.luogu.org/problem/show?pid=1434#sub题目描述Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一... 查看详情

搜索洛谷p1434滑雪

P1434滑雪题目描述Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。... 查看详情

shoi2002百事世界杯之旅|概率论(代码片段)

题目：SHOI2002若当前已经有了x种，再买一个买到不一样的概率为(n-x)/n，要使这个概率变成1，则至少再买n/(n-x)瓶。1#include<cstdio>2#include<string>34longlongmax(longlongx,longlongy)5returny<x?x:y;678longlonggcd(longlongx,longlongy 查看详情

shoi2002百事世界杯之旅(代码片段)

题目链接：戳我看到期望，想着不要从前转移。一次后能买到不同种类的概率为$\fracn-in$两次后能买到不同种类的概率为$\fracin\times\fracn-in$n次后能买到不同种类的概率为$(\fracin)^n\times\fracn-in$设总期望为\(E=\fracn-in\times1+\fracin\... 查看详情

p1291[shoi2002]百事世界杯之旅（概率）(代码片段)

P1291[SHOI2002]百事世界杯之旅设$f(n,k)$表示共n个名字,剩下k个名字未收集到，还需购买饮料的平均次数则有：$f(n,k)=fracn-kn*f(n,k)+frackn*f(n,k+1)+1$移项整理，可得：$f(n,k)=f(n,k+1)+fracnk$根据递推式，可得：$f(n,0)=nsum_k=1^nfrac1k$蓝后g 查看详情

p1291[shoi2002]百事世界杯之旅(代码片段)

题目描述“……在2002年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字，就可参加百事世界杯之旅的抽奖活动，获得球星背包，随声听，更克赴日韩观看世界杯。还不... 查看详情

[shoi2002]取石子游戏-威佐夫博弈(代码片段)

Description有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现... 查看详情

周末学习总结（21.10.23）

...问题：LIS与LCS字符串和多维数组学习笔记P1434[SHOI2002]滑雪心心念念的洛谷账号终于能注册了，再也不用干看着不能交代码了，激动的我先上去见见世面，（看了普及+/提高的简单数论题），好吧，... 查看详情

p1291[shoi2002]百事世界杯之旅(代码片段)

传送门期望DP设f[i]表示还有i个名字没得到，集齐所有名字的期望购买次数考虑一次购买的影响：　　如果得到以前没有的名字f[i-1] -> f[i]，如果得到有的名字f[i]->f[i]那么可以得到f[i]=f[i-1]*(n-i)/n +f[i]*i/n+1（+1是因... 查看详情

[scoi2012]滑雪(代码片段)

贪心+最小生成树一读题目就知道是最小生成树，但是我们显然不能直接跑最小生成树。我们先从1号点跑一遍dfs，记录能到达的点，重新建图，建图时要加入两个端点中海拔较低的那个景点的海拔，之后排序时以海拔为第一关键... 查看详情