L1434滑雪

一,看题

1,这个长度怎么算的。

从它自己数,可以走下去的位置。

2,这个题的衣服怎么披上去呀。

3,搜索目标,状态。

肯定要用坐标,不然怎么搜索。

4,在前期还是多写把。

5,我靠这个点还是随机的》

  ①循环每个点都来下

  ②直接找出最大的点

6,等于咋办》

7,我有点不清楚关于边界性的问题。

8,我不是打擂台了嘛?

既然已经有了记忆化的memor,记录的个点的最长路径?

那么直接在memor这个数组中开一个打擂台的找出最大输出不就完了?

9,我对于这个剪枝又有点疑惑了,我们找的是最大的,最长的,这个剪枝不能这样写把?

10,那我这样写,又和记忆化有什么关系呢》

11,同时我没有用费曼大哥的技巧。

12,能运行,但是样例的答案也不对。

你觉得是哪里错了?既然能输出,那就证明起码和剪枝先关系不大,那么是程序错了,在看看题目和自己对应的程序

你走过的是不是要标记一下》

也就是说之前思考没考虑到标记和回溯

但是感觉又不对,这个要比较大小的,你能从之前的走过来,证明你比他小,你再想走到它那也不行啊。。。

也就是说我在考虑的是每次枚举需要的条件,除了比它小之外,

13,找了一下每次的测试,感觉这个测试数据也太少了,嗯,细节问题,。。

但是感觉怎么又循环了

 14,啊,这就行了,除了你好像多length多加了一次。

15,现在这人总是ac40多分,这让我很蛋疼

   1个tle,剩下的全是WA

 16,还有测试数据的利器,CYARON。。

二,总结

1,这题的关键是要使用记忆化的。。精髓在记忆化,但是你的记忆化嘞。

至少跟上题的记忆化的使用应该不一样,上题棋盘,肯定是要用的是最优化,额

上题的最优化你懂嘛?看看,不总结就是这样,

看来下棋盘这题,棋盘是固定从一个点开始,用这个记忆化还行,滑雪这个题不怎行啊,

所以滑雪这题我该怎么使用记忆化来促进最优化?在这个搜索中我能记录啥东西?

2,而且我发觉我这个结束也并不对,要是人家在里面就走完了呢?所以首先输出答案这里就得改

3,也没给里面数字的范围。但是我这样一初始化,你别想走出这个区域内,所以怎么结束?

所以我现在是被边界性问题给难住了?

4,看了题解我感觉我没懂记忆化,我也没懂搜索。所以说总结和费曼,吃透每道题都很重要。

那么怎么改进

5,每道题要弄透彻,完美写一遍,总结,费曼。

6,操,让我融合一下我就不会了。。

7,枚举为什么多枚举了一次你知道啥嘛?

8,因为要用记忆化去返回那些东西,所以我肯定先int 类型的。

记忆化在于你表示的是个什么东西,能不能和搜索匹配起来,就是要求你对该题的搜索内涵有一个明确的理解。

9,这里的话输出答案我又不会了,是因为跟我之前的模板不一样了。。

int  在里面进行每次的ansmax

void  在外面进行每次的ansmax

10,操换个?

 三,看网课

1,竟然没懂,就是d[i][j]=d[i+1][j]+1,

这个式子我没懂

四,在根据别人的代码写

1,我就奇怪了,明明都一样,妈的,最后输出的时候没有打出个max。。。

2,现在干啥嗯?

3,还是没有彻底理解啊。

4,完美打一遍,总结,费曼。

来跟着我念~

5,我觉我只要能重点理解一下,那个dfs下面那个东西,就可以完美地打一遍了。

memor[i][j],代表的是从i,j点出发,可以到达的雪道的最大长度。问题是假如我就在这里,从这里开始,那么我?

就是不了解递归下去,怎么和这个固定的长度给联系起来。

感觉这步也是那种深入深入地递归进去那种东西。

所以说,对于这种递归的东西,都是知其大意即可。往细节推的话,我估计你会很蛋疼。

6,这个递归主要解决的是记忆化的更新问题。

五,第一遍完美敲打

1,竟然是cin>>b[i][j]错误了。

但是你定义的board。。严肃思考你到底哪里错了

思考本质上你哪里错了

2,反正模块化的检查你是要有的,这都完美的ac不了,我不知道你还能干啥。

3,相信我你错的地方你还会错第二遍,最好的方法是。。。再搞上10遍。。

六,总结

1,我能从中学到什么

①有返回值的搜索和无返回值的搜索怎么写。

②记忆化搜索的一种应用。

2,我犯下了什么错误。

①模块化检查思维的缺失。

3,这道题本质是求什么

①记忆化搜索

4,这道题还可以用别的方法做嘛?

①请看题解

七,费曼

①怎么给别人讲懂这道题?

好像挺难的。

②我直接给赋值ox3f,这个代表?和别人的if(x<1||~~~~)什么的

就像超出这个地点我全埋地雷?

似乎可以来点魔法玄幻的思想

③dfs那么多次也没啥可讲的把。。毕竟人家问的所有的点。函数有返回值也没什么可讲的把。

不断更新最大值好像也没啥可讲的吧?

④,至于dfs,我觉得只是一种思想而已,加上了函数这个形式而已。dfs也可以联系到挖石油,你是逮着一个点不停深挖呢,还是那里挖挖,这里挖挖。

⑤,至于记忆化搜索,我给你还真讲不出来。

难道要用题解里面的那个例子?

在至于这个里面的记忆化更新,那完全就是递归的思想,那么什么是递归?

额,显然用我们斐波那契数列来给你解释一波。

⑥,最后为什么要返回该点x,y下的最长路径?

因为你dfs好像求得 就是这个。。

原文地址:https://www.cnblogs.com/beiyueya/p/11997707.html