CF DP 题乱做（续更）-526互联

CF566F

$1500$

容易考虑到 $n^2$ 做法：设 $dp_i$ 为第 $i$ 个数选的答案，对于排好序的序列，枚举前面的数 $a_j$，如果 $a_j|a_i$ 就转移，时间复杂度易知 $O(n^2+n\log n)$。

由于 $a$ 至于很小，延续刚才的思路，设 $dp_i$ 为选值为 $i$ 的答案。那么她可以更新她的所有倍数，枚举倍数即可。

考虑到 $a_i$ 互不相同（我也不知道怎么知道这个条件的，但是不去重直接算能过），那么极端情况就是 $\sum\limits_{i=1}^{n}\left\lfloor\dfrac{n}{i}\right\rfloor = n \log n$ 所以可以通过。

CF264B

$1500$

容易写出 $dp_i$ 记录选第 $i$ 个数的答案，可以由 $j$ 满足 $\gcd(a_i,a_j)>1$ 转移过来。

但这太慢了，考虑我提前搜出来每个数的因数，同时维护一个 $f_i$ 表示因数为 $i$ 能得到的最大贡献，这样大大减少了枚举数量，可以通过此题。

有转移：

$dp_i = \max{f_j}+1$

CF474D

$1700$

设计 $dp_i$ 为长度为 $i$ 的方案数，那么她要么是 $0$，要么是 $1$，如果是 $0$，那么她的上一位就没限制，所以从 $i-1$ 转移过来；是 $1$，那么前 $k$ 位就都得是 $1$，所以在此区间只有一种方案，所以应从 $i-k$ 转移过来。

有：$dp_i = dp_{i-1} + dp_{i-k}\times[i\ge k]$

初始化 $dp_0 = 1$

前缀和一下即可。

CF580D

$1700$

看数据范围可知是状压，考虑 $dp_{S,i}$ 为吃了 $S$ 集合里的，最后吃的是 $i$。

枚举集合 $S$，记录 $popcount$，如果刚好是 $m$，统计一轮答案。如果比 $m$ 小，则有转移：

$$
dp_{S+i,i}= \max{dp_{S+i,i},dp_{S,j}+a_i+c_{j,i}}
$$

枚举 $i$ 是接下来要吃的，$j$ 是刚刚吃完的。

时间复杂度 $O(n²²n+n+k)$ 可以通过此题。

CF1635D

$1800$

考虑把这些数当做二进制处理，对 $1e5$ 的 $p$ 来讲更加友善。

那么对于她讲的这两个操作，本质就是要么在二进制末尾添加一个 $1$，要么就在后面添加两个 $0$。

那么得到转移 $f_i = f_{i-1} + f_{i-2}$，总方案数就是求和，那么就是求一个 $fib$ 部分和。

考虑多算了一些东西，就是有可能一个大数是可以由一个小数变化而来的，那么就不应该计算她，因为是重复的。考虑从小到大排完序后，每次暴力的去模拟往前找，如果找到了一个已经存在的，说明她是可以被前面的变化过来的，就把她删了好了。

最后数一数她有多少位，加起来就好了。时间复杂度 $O(n+p+n\log n)$，当然我知道，$fib$ 前缀和可以做 $\log p$，在此不赘述，毕竟 $1e5$ 没必要。

CF41D

$1900$

考虑设 $dp_{i,j,k}$ 为到 $(i,j)$ 时能否收集 $k$ 个豌豆。

那么就有转移方程：

$$
dp_{i,j,k} = dp_{i+1,j-1,k-a_{i,j}} \text{ or } dp_{i+1,j+1,k-a_{i,j}}
$$

初始化 $dp_{n+1,i,0} = 1$。

从大到小枚举倍数，找可以达成的位置，找到了从下到上输出方案即可。

CF1627D

$1900$

$\gcd(\gcd(a,b),c) = \gcd(a,b,c)$，所以我生成了一个 $\gcd$ 后，拿着她去跟别的生成的 $\gcd$ 就是她们本身全体的 $\gcd$，由此，问题被简化成了在这个序列里乱选一些数，能得到多少个不同的 $\gcd$。当然，肯定不会同一个数选择多次，因为这样不会有贡献。

那么考虑直接暴力计算那些数是可以被若干次 $\gcd$ 凑出来的。我们发现一个数的若干个倍数的 $\gcd$ 可能是她本身（当然也有可能是她的倍数），那我们就枚举她的已经存在的倍数，全 $\gcd$ 起来，判断是不是她本身且她不在原有集合里就可以记录答案，因为调和级数是 $\log$，所以时间复杂度 $O(n\log n)$。