1 条题解
-
0
B 禁忌的联盟 (lol) 题解
Step 1: 忽略 颜色限制,只处理 不互质
定义DP状态
定义一个DP状态:
f[p],表示以质因数 为最后一位因子的最长子序列长度。转移方式
观察到,如果两个数 有公共质因数 ,那么它们之间可以相连。
对于每个 ,我们枚举它所有的质因数 ,找到所有 中的最大值 ,然后令当前元素作为结尾的子序列长度为 ;然后反向更新所有这些质因数的 。
这个部分的复杂度是 ,因为对每个 做质因数分解。
Step 2: 引入 不同的限制(颜色限制)
每个质因数 下,维护两个记录:
f[p].max1:最大的子序列长度,以及对应的f[p].max2:第二大的子序列长度(必须与max1的 不同)
转移逻辑
对于当前元素 ,设 的所有质因数集合为 ,我们尝试从这些质因数对应的最长记录中转移:
$$dp[i] = \max_{p \in P} \begin{cases} f[p].\text{max1}.\text{value} & \text{if } f[p].\text{max1}.\text{color} \neq a_i \\ f[p].\text{max2}.\text{value} & \text{if } f[p].\text{max1}.\text{color} = a_i \end{cases}$$然后将 更新回所有 的
f[p]中对应的位置。总复杂度:,其中
信息
- ID
- 218
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 4
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者