首页 > 其他分享 >洛谷题单指南-动态规划1-P1434 [SHOI2002] 滑雪

洛谷题单指南-动态规划1-P1434 [SHOI2002] 滑雪

时间:2024-04-18 17:23:52浏览次数:27  
标签:ni int 洛谷题 滑行 nx ny P1434 SHOI2002 dp

原题链接:https://www.luogu.com.cn/problem/P1434

题意解读:计算能滑行的最长距离。

解题思路:

设dp(i, j)表示从i,j可以滑行的最大距离

对于4个方向i,j可以到达的点,ni,nj,如果可以滑过去(ni,ni所在点高度更低)

则dp(i, j) = max(dp(i, j), 1 + dp(ni, nj))

为了便于搜索4个方向的各条路径,采用dfs递归形式更便于操作

而每个点所能滑行的最大距离在递归过程中会多次重复计算,因此可以采用记忆化搜索,保存已经计算过的结果。

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
int r, c;
int a[N][N], f[N][N];
bool flag[N][N];
int ans;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

//从x,y开始能滑行的最大距离
int dp(int x, int y)
{
    if(f[x][y]) return f[x][y]; //记忆化,如果已经计算过直接返回
    int res = 1; //任意点可以滑行的初始距离为1
    flag[x][y] = true;
    for(int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if(!flag[nx][ny] && nx >= 1 && nx <= r && ny >= 1 && ny <= c && a[nx][ny] < a[x][y])
        {
            flag[nx][ny] = true;
            res = max(res, 1 + dp(nx, ny)); //dfs搜索所有路径,取长度最大的
            flag[nx][ny] = false;
        }
    }
    return f[x][y] = res; //记忆化,保存滑行距离
}

int main()
{
    cin >> r >> c;
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= c; j++)
            cin >> a[i][j];
    
    for(int i = 1; i <= r; i++)
    {
        for(int j = 1; j <= c; j++)
        {
            memset(flag, 0, sizeof(flag)); //重置flag
            ans = max(ans, dp(i, j)); //从每一个点开始dfs搜索路径
        } 
    }
    cout << ans;
    return 0;
}

 

标签:ni,int,洛谷题,滑行,nx,ny,P1434,SHOI2002,dp
From: https://www.cnblogs.com/jcwy/p/18143989

相关文章

  • 洛谷题单指南-动态规划1-P2196 [NOIP1996 提高组] 挖地雷
    原题链接:https://www.luogu.com.cn/problem/P2196题意解读:求一条路径,使得所有点地雷数之和最大。解题思路:1、DFS先建图,再从1~n点分别进行一次DFS,记录过程中地雷总数最大的,并且同时记录遍历的顺序。数据量不大,直接就可以过。100分代码:#include<bits/stdc++.h>usingnamespa......
  • 洛谷题单指南-动态规划1-P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles
    原题链接:https://www.luogu.com.cn/problem/P1216题意解读:计算数字三角形最高点到最后一行路径之和最大值,典型线性DP。解题思路:设a[i][j]表示数字三角形的值,设dp[i][j]表示从最高点到第i行第j列路径之和的最大值,由于每一步可以走到左下方的点也可以到达右下方的点,所以dp[i][......
  • 洛谷题单指南-数学基础问题-P1403 [AHOI2005] 约数研究
    原题链接:https://www.luogu.com.cn/problem/P1403题意解读:计算1~n每个数的约数个数之和。解题思路:1、数学方法1~n的约数范围也在1~n,要计算每个数的约数个数之和可以从约数出发,比如约数是x,那么在1~n中一共有n/x个数包含x这个约数x从1一直枚举到n,就可以得出每个约数是多少个......
  • 洛谷题单指南-数学基础问题-P3601 签到题
    原题链接:https://www.luogu.com.cn/problem/P3601题意解读:求l~r范围内所有qiandao(x)之和,qiandao(x)为小于等于x的数中,与x不互质的数的个数。注意取模。解题思路:欧拉函数定义:phi(x)=x*(1-1/p1)*(1-1/p2)*...*(1-1/pn),p1,p2...pn为x的所有质因子其中:phi(x)表示1~x中所......
  • 洛谷题单指南-数学基础问题-P2660 zzc 种田
    原题链接:https://www.luogu.com.cn/problem/P2660题意解读:对一个长方形,切割出最少数量的正方形,计算所有正方形的边长。解题思路:长方形长、宽为x,y先判断x,y哪个长,哪个短长的作为l,短的作为s先切出s*s的正方形,一共可以切出l/s个,累加周长ans+=l/s*s*4在对剩下的s*......
  • 洛谷题单指南-数学基础问题-P2651 添加括号III
    原题链接:https://www.luogu.com.cn/problem/P2651题意解读:计算能否在除法a1​/a2​/a3​/.../an​式子中加括号,将一部分数变成分子,使得除法结果是整数。解题思路:在a1​/a2​/a3​/.../an​中,无论怎么加括号,a1一定是分子,a2一定是分母,那么可以判断把a3...an都作为分子,是否能除尽......
  • 洛谷题单指南-数学基础问题-P1414 又是毕业季II
    原题链接:https://www.luogu.com.cn/problem/P1414题意解读:有n个数,从其中选k个数,k=1,2,3......n,使得这k个数的gcd最大。解题思路:如何求k个数的最大公约数呢?暴力法肯定不行。可以从1到n枚举这个最大公约数i,看是否有>=k个数的因数是i具体来说,用桶数组存放所有整数,a[x]表示x的......
  • 洛谷题单指南-数学基础问题-P1572 计算分数
    原题链接:https://www.luogu.com.cn/problem/P1572题意解读:计算分数+、-运算的结果。解题思路:根据题目要求,逐项计算并约分,则不会超int,问题就比较直接了定义a1/b1为前一项的分子分母,a2/b2为当前项的分子分母依次遍历字符串,处理出分子和分母,本题的关键其实是字符串的处理当读取......
  • 洛谷题单指南-数学基础问题-P4057 [Code+#1] 晨跑
    原题链接:https://www.luogu.com.cn/problem/P4057题意解读:给定三个数,计算其最小公倍数。解题思路:三个数a、b、clcm(a,b,c)=lcm(lcm(a,b),c)100分代码:#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;LLa,b,c;LLgcd(LLa,LLb){i......
  • 洛谷题单指南-数学基础问题-P1069 [NOIP2009 普及组] 细胞分裂
    原题链接:https://www.luogu.com.cn/problem/P1069题意解读:一个数s代表细胞经过一天分裂的个数,则经过t天后个数为st,要计算经过几天后能整除m1m2,也就是st%m1m2==0,有多个s,要计算天数最少就可以满足条件的。解题思路:直接求st%m1m2显然不可取,会超出整数最大范围,高精度也不是好......