louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共2篇）

题解 | 算法竞赛进阶指南赤壁之战

思路设计状态表示最后一个数为,长度为的严格递增子序列个数.我们可以轻松地推出转移方程: 注意到这两个限制是二维的,第一维直接按顺序枚举不断加入状态即可解决,第二维套一个树状数组即可解决.因为可能很大需要离散化.复杂度为看起来有点大,但是因为树状数组常数小,还是可以过的.实现中为了减小内存使用了滚动...

树状数组计数类动态规划动态规划

2019-08-26

0 780

题解 | 算法竞赛进阶指南杰拉尔德和巨型象棋

思路因为较大,不能直接用和设计状态.将染成黑色,题目变成求从开始,第一个经过的黑色格子是的路径有多少.先将所有点排序,第一关键字为所在行,第二关键字为所在列.设为从开始,第一个经过的黑色格子为的路径条数.首先,.假设之前不经过任何黑格子,那么.然后减去之前经过黑色格子的路径.枚举这些路径经过的第二...

计数类动态规划动态规划排列组合

2019-08-25

0 603