CF264B Good Sequences 的题解

· 2024-11-02 · # 动态规划 # Codeforces # 题解

考虑设 $f_i$ 表示以 $i$ 结尾的串的最长长度，那么容易想到转移：

f_{a_i}=\max\limits_{j=0}^V f_j\times[\gcd(a_i,j)\ne 1]

考虑怎么优化，设 $g_i$ 表示所有包含因子 $i$ 的最大的 $f$ ，这样转移就只需要枚举自己的因子就行了，时间复杂度为 $O(n\sqrt{V})$ 。