本篇很高能,如有错误欢迎指出,本人能力有限(需要前置知识记忆化dfs,树形dp,bfs+dp,tarjan) 另外,本篇之所以属于图论,也是想让各位明白,dfs就是就是在跑图!如果dfs离开了图论的知识将会困难重重 记忆化dfs可以看这里 【算法每日一练]-记忆化dfs (保姆级教程 篇4)#滑雪 #天下 第一 #切木棍-CSDN博客 树形dp可以看这里 【算法每日一练]-动态规划 (保姆级教程 篇6(树形dp))-CSDN博客 tarjan可以看这里(这个是重点) 【看不懂你来打我]-图论(保姆级教程篇11 tarjan)无向图的桥 ,无向图的割点 ,有向图的强连通分量-CSDN博客
先来题目引出问题: 题目:跳棋
碎碎念部分:(如果你有兴趣可以看一下,如有错误欢迎指出,本人能力有限) 题意就是从0的地方选四个方向,跳到下一个0的地方,重复,问问你最远能走多远? 那么我就寻思好嘛,太常见了:我反手就是f[x][y]=max(dfs[下一个0坐标]+当前0坐标到下一个0坐标的距离),然后设置f[x][y]表示从当前点出发能走的最远距离。这样的话还能记忆化加速,我去,我可太聪明了!下面是我的伪代码:
然后外面的dfs再加上记忆化和返回值步骤即可。欧了,输入样例---------跑的什么玩意???
其实这段代码问题很大! 首先就是vis数组和dfs(下个状态)非常冲突,因为你设置的f[x][y]表示以此为起点去跑,可是你在dfs下一个状态时候的它的vis都不是清空的,它的返回的f结果怎么可能会是对的呢?想要使得下一个状态的结果是正确的就应该让它以起点单独跑,你以为这样就行了? 还是错!因为它的下一个状态还会遇到相同的问题,那么返回的结果也不对,( 还有一点是记忆化那里:if(f[此状态来过])return f[此状态]。 这句话也不对,因为它的前提是你的f状态的结果是正确的,如果现在还不是正确的,那不应该继续跑它吗?而不是直接去使用呀,所以这句话也不能有! 以上的思路都是来自之前做过的一道滑雪的题。(在开头哪里有,你可以去看一看) 然后我们来对比一下之前做过的“ 滑雪 ”那道记忆化题: 在那个题中,我们设置f[x][y]表示从此点为起点跑的最远距离,然后有f[x][y]=max(f[x][y],dfs(下一个点)+1),之所以这个式子是正确的,是因为它后面的dfs(下一个点)的结果是正确的!那为什么下一个点的dfs是正确的呢?是因为它下一个dfs的结果是正确的,那么为什么它下一个结果是也是正确的呢?是因为它每个下层状态都不依赖于前面的dfs结果,也就是没有环!也正因为没有环,这个dfs的结果一定是正确的。也就是不会改变的,既然都不会再改变,那以后再遇到这种情况还跑啥呀直接使用结果呗,所以就可以记忆化去省时间,它的模式是类似树形dp的,就是不会遇到环。 到这里,你就发现了本题出问题的原因是有环!也就是你的下一个状态要想正确的跑出来,就依赖于之前的状态,但是之前状态的正确性又要靠后面去跑,所以这样去设置f[x][y]的含义是非常不应该的。所有有环的dp都非常危险,无论是你是循环dp还是dfsdp,都不是很妥的。而树形dfs一般都可以来dp,也可以记忆化。 另外,递推一般可以记忆化,搜索当然也可以记忆化,而有环一般就不行了。当然有环一般伴随着回溯。 说了这么多。赶紧回来回来 思路:本题明显适合搜索,而不是递推。 我们可以直接去搜索跑的,并不会超时,每dfs一个点就先更新一下答案,然后找到下一个0点坐标,如果有的话且没有走过就跳过去,然后从那个点继续跑,回来时候再清空标记。重复。 一套流程行云流水就打出来了。代码如下:
题目:奶牛隔间
一开始思路是模拟,后来看到隔间数和奶牛数……好吧不行,那应该就是dp了,循环dp我不太会写,dfsdp应该可以的,好的,那么我们开始写: 设置f[x]表示从x开始访问的隔间数,那么因为从x隔间走,访问的隔间数是一定的,故而可以记忆化节省时间,那么反手就是: f[x]=dfs(下一个隔间)+1;然后这个式子我是越看越迷糊,下一个隔间要想成功遍历,和上一个状态很冲突啊!因为从下一个隔间为起点的话,当前的隔间x就不能被标记呀,看到了吗?下一个状态会跑到前一个状态,你告诉我这能dp? 思路:根据题意,一只奶牛停止的条件是来到她所经过过的房间,也就是奶牛想要停下来必须要找到一个环。看到了吧,这是有环的,那么我们也有tarjan啊。来吧! 首先明显是有向图,我们跑一下tarjan把那些环划到一起,然后把环看成一个整体,或者把整个图看成是许多个强连通分量(为什么?因为无论这个环从哪个点进入,返回结果都是一样,都是环长),我们在这些强联通分量之间建立指向关系,然后就可以树形dp了,当然也需要记忆化(不然还是超时)另外提示一下:强联通分量中节点数就是环上点的个数。
题目:小A和uim之大逃离 II每个点都有两种状态,问你能不能走出去,可能有人想循环dp,但是这个绝对不能循环dp。 因为循环dp的顺序非常有问题,导致在转移的时候有多点还没有更新就已经被转移了,是必错的结局!那么正解是什么呢? 我认为bfs+dp是最好的,因为bfs是按层跑的,dp应该按层去转移,才是最正确的! 思路:对于本题,每个点都有两种,如果只有一种,那么就很好转移;但是如果有两种,那么不妨就保存两种点。 当从当前点cur.x和cur.y准备走到下个点x,y时: 如果到下一点不嗑药,无论u是0还是1,那么都是st[x][y][cur.u]=st[cur.x][cur.y][cur.u]+1。然后入队 千万注意顺序,一定是先不嗑药在前面,把st[x][y][0]更新正确,然后才是考虑这个点嗑药。你当然可以理解成嗑药的话相当于走了两步!(也没有人说bfs的所有点都只能一次走一步啊) 补充: 你会发现这些转移都是具有唯一性的,也就是说仅转移一次。
看到这里,你果然是高手。 |
原文地址:https://blog.csdn.net/m0_69478376/article/details/137013786
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:https://www.msipo.com/article-659711.html 如若内容造成侵权/违法违规/事实不符,请联系MSIPO邮箱:3448751423@qq.com进行投诉反馈,一经查实,立即删除!
Copyright © 2024, msipo.com