ARTS打卡 第十五周

ARTS打卡 第十五周

首先是算法，本周leetcode还是有很多有意思的题目的

题目 这道题的O(n)的做法还是比较好的，感觉是一个较有启发性的思路

然后是今天周赛的题目

题目 这个是求不同子序列的数量的一个变式，如果理解的清楚的话可以很容易把这个变式写出来。但是这道题的基础版，求解不同子序列的dp还是很有意思的。对于每一个数，如果他是第一次出现，那么他的贡献是前面所有子序列的和，因为前面的子序列都可以加上他来形成新的答案。同时他也可以自己为头，就再加上1。如果他不是第一次出现，那么我们需要减去他上一次出现所造成的贡献，然后再把这一次新的加上。

即如果a[i]是第一次出现，那么dp[i] = 2 * dp[i - 1] + 1 //因为要加上原来的

否则dp[i] = 2 * dp[i - 1] - dp[last[a[i]]]

题目

这道题的状压dp也很不错，属于经典问题，就是若干个分组，满足每个分组总和不大于一个数的前提下，最少能分多少组，应该是np问题

这周总体来说有点划，因为上周结束了GSoC导致这周有点放纵，折腾了很多在linux上玩windows游戏的方法，都成功了，现在可以快乐的玩warframe和sc2了

然后还在继续看程序员的自我修养，看完了动态链接的部分，这周争取看完这本书。

还有要说的一点是我重装系统换成了ubuntu20，感觉还不错，支持了很多新东西。