首页 > The Battle of Chibi
开通博客写题解
头像 Dear㉿You
发表于 2020-10-23 16:59:05
The Battle of Chibi 分析 这题不用优化?状态设计：设f [ i ] [ j ] ：长度为 i ，以 a [ j ] 为结尾的严格上升子序列如果要优化的用树状数组+离散化，可以减少一重循环 代码(普通) int T;scanf("%d",&T); for ( 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 louhc
发表于 2019-08-26 21:07:43
思路 设计状态表示最后一个数为,长度为的严格递增子序列个数.我们可以轻松地推出转移方程: 注意到这两个限制是二维的,第一维直接按顺序枚举不断加入状态即可解决,第二维套一个树状数组即可解决.因为可能很大需要离散化.复杂度为看起来有点大,但是因为树状数组常数小,还是可以过的.实现中为了减小内存使用了滚动 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”