<---- 麻烦点一下旁边向上的三角形
推销一下:
$\color{#00FF7F}{算法提高课 第一章 动态规划 全题解(正在完善)}$
题目描述
给定一个 $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
梳理一下题目含义:
给定一个$R$ 行 $C$ 列的矩形网格滑雪场
一个人从滑雪场中的某个区域内出发,每次可以向上下左右任意一个方向滑动一个单位距离。
当然,一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
注意:
那个人可以从矩形网格滑雪场的任意一点出发
可以上下左右移动
每次只能滑一个单位距离
这个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度
解释一下样例:
看懂了题目,现在我们来看看样例输出为什么是$25$。
如图:
字丑了点QWQ,不管它了,继续!
算法1
(动态规划) $O(n^2)$
这道题用$bfs$肯定会超时,毕竟题目已经明确指出这道题是动态规划问题
所以我们这道题可以用动态规划做。
$DP$分析图如图:
讲解一下状态计算的部分:
如图:
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 310;
int n,m; //网格滑雪场的行和列
int f[N][N]; //状态转移式
int h[N][N]; //网格滑雪场
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int dp(int x,int y){
int &v = f[x][y]; //Y总说的小技巧,等于把f[x][y]简化成了v,如果v发生变化,f[x][y]也会随之变化
if(v != -1) return v; //如果已经计算过了,就可以直接返回答案
v = 1; //注意v要先赋值为1哦~
for(int i = 0;i < 4;i ++){ //四个方向
int xx = x + dx[i];
int yy = y + dy[i];
if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && h[x][y] > h[xx][yy]){ //判断这点是否能走
v = max(v,dp(xx,yy) + 1); //更新
}
}
return v; //别忘了返回v啊(被坑了
}
int main(){
cin>>n>>m; //输入滑雪场行和列
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
cin>>h[i][j]; //读入滑雪场数据
}
}
memset(f,-1,sizeof f);
int res = 0; //最后答案
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
//因为这个人可以在任意一点开始滑,所以要遍历一遍滑雪场
res = max(res,dp(i,j)); //更新答案
}
}
cout<<res<<endl;
return 0;
}
注意:
要记得把$f$数组初始化为$-1$
定义$v$的时候注意要加上$&$
如果这个点没计算过,$v$记得要赋值为$1$
$v = max(v,dp(xx,yy) + 1)$ 不要忘了 $+1$
记得要返回$v$
$$(共172行)$$
给哥们点点举报哈哈 写得好滴
集合表示的是从$f[i,j]$开始滑的所有路径,那应该是从$f[i,j]$滑到$f[i,j+1]$,你的图画反了
最后一张图吗,刚刚在写题解没看到QWQ
我觉得没毛病啊对的,最后一张图右上角应该是是哪个从中心点到上下左右四个方向,不是从上下左右四个方向到中心点,因为状态集合是从$f[i,j]$开始,并不是到$f[i,j]$
我来解释一下为什么要让v=1,以防有跟我一样疑惑的兄弟浪费时间
把v设置成1,因为最次最次的情况下,还是在当前格子,不要把从一号点走到二号点的距离想成是1了,其实是2,两个点路径是2,因为题目是用点来表示路径长度的,所以要让v=1因为第25行代码赋值的时候假如dp(a, b)不能往后走了那么从(x, y)走到(a, b)点的路径就是2(点的数量),因为dp(a, b)里面会把f[a][b]赋值为1,然后+1就等于2了,然后再通过max函数赋值给f[x][y]
有一个小细节不知道自己理解的对不对
在
if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && h[x][y] > h[xx][yy])
这句最后一个判断:h[x][y] > h[xx][yy]
感觉应该把大于号改成小于号,也就是h[x][y] < h[xx][yy]
因为根据闫氏dp法,正如上面那个状态分析的图所述,是“滑过来”而不是”滑过去”,也就是说是从上一状态(xx,yy)变到当前(x,y)的状态,那么是不是应该(x,y)应该作为一个较低的“坑”?
不过,因为都是单调的,所以问题是对称的,大于小于号并不影响答案结果,不过秉持闫氏dp法为指导思想,我感觉思维上需要明确一下(本人菜鸡,理解有错的话感谢佬们指出!)
对的。我也这么想的
起点是[x,y]将要到达的点是[xx,yy],h[x,y] > [xx,yy]没毛病
我感觉,一开始带入的坐标是(1,1),所以起点是从(1,1)开始的,但1小于任何一个点,所以不会向下滑,我感觉作者是向上滑的意思,本人真菜鸡,个人理解,错了勿喷,请大佬指错
本篇题解作者在划分集合的时候,四个集合分别是从上下左右四个方向“滑过来”的,而按照作者这么划分的话,$f[i][j]$ 表示的状态其实应该是 “一条路径中最后滑到的点是$(i, j)$” ,换句话说,若要从上下左右四个点滑到$(i, j)$,则$(i, j)$的高度要比上下左右四个点的高度低,才能“滑过来”,所以此时判断条件应该为
h[x][y] < h[xx][yy]
。但是本篇题解中,作者对 $f[i][j]$ 状态的定义为 “所有从$(i, j)$开始滑的路径”,那么此时四个集合就应该是从$(i, j)$向上下左右四个点滑,$(i, j)$的高度要比上下左右四个点高才能“滑过去”,所以此时判断条件应该为
h[x][y] > h[xx][yy]
。所以其实本篇题解是有点问题的…作者对$f[i][j]$的状态定义和集合的划分是不相符的。但是其实这样也无伤大雅,我上述所说的两种$f[i][j]$的状态定义,它们两个的状态计算是一毛一样的,但就严谨性来说,这里的判断条件的确应该是
h[x][y] < h[xx][yy]
。hhh大佬说的好有道理ORZ,不如把题目变一变,“滑雪问题”变成“登山问题”,需要往高爬,本质上好像也是一样的,就是把滑雪倒过来
没错没错hhh 这两个问题本质上都是一样的qwq
感觉有点区别
当
g[x][y] > g[a][b]
时,该题f[3][3]
是最长的。f[i,j]
表示从(i,j)
出发滑下去的最长轨迹。当
g[x][y] < g[a][b]
时,该题f[1][1]
是最长的。f[i,j]
表示从(i,j)
出发爬上去的最长轨迹。这里规定了不能出界,所以在所有点中,最长滑行轨迹的最高点和最低点在同一个滑行轨迹中,因此答案是一样的。
如果要简化
a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[a][b]
将外围初始化为INF
memset(g, 0x3f, sizeof g);
上式就只能简化为
g[x][y] > g[a][b]
将外围初始化为-INF
memset(g, -0x3f, sizeof g);
上式就只能简化为
g[x][y] < g[a][b]
这里也能看出两者区别。
NB
QwQ
集合划分那里是有点问题的,你对$f[i][j]$的状态定义为“所有从$f[i][j]$开始滑的路径”,所以集合应该是从$f[i][j]$向上下左右四个点滑过去
若要是按你这样划分集合的话,其实对$f[i][j]$状态的定义应该改为“一条路径上最后滑到的点为$(i, j)$”qwq
QwQ暑假了才有时间处理问题
现在在改了
改好了QwQ
巨佬麻烦看一下对了没有
为啥v要赋值为1
滑的次数加一啊
现在不是多滑了一次吗,那肯定这里的值是要加一的啊
v = max(v,dp(xx,yy) + 1); 这里不是加一了吗
哦哦不好意思看错了
无论你从哪个地点开始滑,那么这个地点也在滑过的路程里
所以按照题意,第一次站的位置也算滑了一次
啊哈哈哈哈 没有没有 我也是萌新啦qwq 应该是对了吧 我现在在准备考研 已经两个月没碰算法题了 现在回头再看这些题发现跟看天书一样哈哈哈qwq
加油哈!我感觉你很强!qwq
QwQ
太强了 清晰又易懂
哪位大佬能看看哪里错了
#include[HTML_REMOVED]
#define N 306
using namespace std;
int r,c,h[N][N],dp[N][N];
int rans;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int DFS(int i,int j){
int &cnt=dp[i][j];
if(cnt!=-1) return cnt;
cnt=1;
for(int m=0;m<4;m){
int nx=dx[m]+i,ny=dy[m]+j;
if(nx<=c&&nx<=r&&nx>=1&&ny>=1&&h[nx][ny][HTML_REMOVED]>r>>c;
for(int i=1;i<=r;i){
for(int j=1;j<=c;j){
cin>>h[i][j];
}
}
memset(dp,-1,sizeof dp);
for(int i=1;i<=r;i){
for(int j=1;j<=c;j++){
rans=max(rans,DFS(i,j));
}
}
}
输入
1 1
1
输出2 正解1
用一下markdown。。。。
不用了,大佬,我找到了是因为边界判断出了问题
小尴尬
tql
QwQ
感觉这题更像dfs
记忆化搜索嘛,但是我觉得更像bfsQwQ
热知识:变量前加&,是声明了一个引用,引用的对象就是等号后面的东西,可以理解为引用是对象的别名,调用引用就是在调用对象。和指针类似,但不会出现野指针,空指针之类的危险情况
%%%
话说我刚刚调完一段代码就是scanf忘加&。。。。为什么x的坐标的边界是n啊x不是左右移动的吗边界不应该是m吗
应该是x是行,y是列吧
99999999999
为什么在新一轮dp中,不用更新 f 数组呢
f数组已经用v = 1 更新了
dp跟深搜搞一起…
为什么前面计算过的路径后面能用? 比如从第一个点滑的路径已经算过,从3,3点开始计算的路径,dp中直接调用1滑的路径可能和当前走过的路径相交,从而产生冲突
哥们,你理解了没,我也不理解
遇到之前路径上的点,不会有别的路径比之前算的路径更优
这道题的dp实现方式只能用递归吗?
应该有其他办法的
因为这个你在计算(i, j)的时候需要从(i+1,j),(i,j+1),(i+1,j+1)转移过来,但是还没有计算,所以通过递归形式计算dp值
字好看
额
走迷宫那道可以用记忆化搜索计算有多少条路径吗
关于走迷宫类型的题,如果要求多少条路径,那就只能用DFS来做,就是用爆搜把所有可能都找出来;如果要求最短最长路径,可以用DFS,BFS和DP记忆化搜索,DFS和BFS其实是一类的,都必须知道路径的起点和终点,区别在于一个用递归,一个用队列;DP的优势在于它给出的是状态计算方程,你想要什么样的结果,只需要把任意路径的起点和终点放到状态方程里去遍历就可以了