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(n22n+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)$。
CF295C
$2100$
考虑设 $dp_{i,j,k}$ 记录第 $i$ 轮划船岸上有 $j$ 个 $100$ 斤, $k$ 个 $50$ 斤 的方案数。
显然,若某一时刻 $dp_{i,0,0}$ 有值,那么就输出。
转移为:枚举一次运输了 $a$ 个 $100$ 斤,$b$ 个 $50$ 斤
对于去:
$$
dp_{i,j,k} = \sum calc(x,a,y,b)\times dp_{i-1,j-a,k-b}
$$
对于回:
$$
dp_{i+1,j,k} = \sum calc(x,a,y,b)\times dp_{i,j+a,k+b}
$$
我们有函数 $calc(x,a,y,b) = \dbinom{x}{a}\dbinom{y}{b}$
CF1650F
$2200$
考虑 $0-1$ 背包,考虑到数据范围,我们设时间为价值,百分比为容量,那么容量就从 $0\sim200$,对于每个任务做背包,然后看在规定时间内能否完成任务,即是否有 $100%$ 以上有值。按常规套路输出方案即可。
有状态转移:$dp_{i,j} = \min{dp_{i,j},dp_{i+1,j-p_i} + t_i}$
这个题细节比较多,尤其注意初始化时不要用 memset
,否则会超时。