相融子列题解

设f[i][x]表示前i个数中,结尾的数含有因子x组成的最长子序列的长度。
每次新加进来一个数,只需要枚举这个数包含的质因子即可。
由于f[i][]的值可以只与f[i-1][]有关,所以可以省去一维。
最终复杂度O(nlogn)

全部评论

相关推荐

想顺利毕业的猕猴桃在看牛客:好几个月没面试了,腾讯留面评吗
点赞 评论 收藏
分享
2024-12-25 09:09
四川师范大学 运营
想和你交朋友的潜伏者要冲国企:先去沃尔玛亲身感受标准化流程体系,一两年后再跳槽国内任何零售行业,可以有更大选择权吧?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务