ARTS打卡 第三周
最开始感觉ARTS打卡还蛮容易的，每周只要做一次就好，甚至曾经还妄想每天一次
现在发现自己确实没这么多时间
上周主要的时间都用来取搞学校里的课程设计，实验，大作业了，感觉自己的提升不是很多，书也没看多少
不过最基本的底线，还是每天保证刷算法题至少达到了，周赛也打了，不过最近发现自己已经快做不出第四题的样子了
这周的算法题有两个值得说一说
读完题就可以很明显的发现是一道dp了，我们是在区间中取最值，且满足最优子结构的性质，所以可以发现这是一个区间dp
这道题有意思的点是状态转移
很显然的是枚举区间端点后再枚举断点，然后从两个子区间中转移过来
而对于两端点相同的情况下，我们就很容易的想到一个策略，就是只要端点相同，我们就不断的向子区间搜索
但是这样的复杂度在某些情况下会变得很高
题解给出了状态转移式 dp[i][j] = dp[i][j - 1] when (a[i] == a[j])
十分精妙的转移式，相当于端点相同时，右端点的字母是我们白嫖来的
第二道题是周赛的题
这里我用了差分数组来解决这个问题
对于一个点i来说，我们将其能跳到的位置(i + minJump) ~ (i + maxJump)区间加一
这样对于任意一个点i，如果他是可以被跳到的位置，当且仅当他的权值大于0，且s[i] == 0
我们手动给0号点加1，对于区间加一，同时最后求单独一个点的值的情况，差分数组是最合适的了
技术的文章的话，我这周要推荐这个
这篇文章是教我们在树莓派的裸机上编写操作系统的，文章里提供了基本的接口
我根据这个接口，适当的进行了修改，并移植了两个小游戏进去，分别是飞扬的小鸟和俄罗斯方块
正好也是受到了前一阵tetris-os的启发，做出了这个东西，github地址
对于观点方面的文章，我推荐这个
引起了自己一定的共鸣，因为我自认为并不是一个适合取打算法竞赛的人，我的爱好还是在于开发，这段时间与scummvm社区的人一起开发开源项目真的让我受益匪浅
之后我打算分享一定的书，因为自己平常看文章并不是很多，还是看书相对多一些，所以在之后的分享中，我希望可以分享一些书中的内容
文章评论