louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共16篇）

题解 | 算法竞赛进阶指南蒙德里安的梦想

思路都这么小可以考虑考虑状态压缩.表示填了前行,只有第行还有一些位置没有填过(满足). 可以从上一种状态转移过来需要满足以下条件: 每段连续的都是偶数个. 因为数据范围比较小,并且你也不知道询问有多少,可以预处理出所有可能输入的答案(当然也可以打表,虽然好像不太厚道),然后每次询问直接输出答...

状态压缩动态规划

2019-08-26

0 1028

题解 | 算法竞赛进阶指南炮兵阵地

思路 ,这么小的数据范围当然要想到状态压缩.我们把放置炮兵的位置变成,不放炮兵为.这题比较猥琐的一点就是会影响到能否放炮兵的有前两行.这样至少需要三维,记录当前到哪行以及前两行的状态.这样不能承受.由于这特殊的"十字",每行两个炮兵之间至少要两个格子.打个表可以发现满足条件的状态大概只有六十几个,这...

状态压缩动态规划

2019-08-26

1 637

题解 | 算法竞赛进阶指南积蓄程度

思路假设源点已经确定为1,那么直接跑树形DP即可.表示到叶子节点的最大流量(不考虑父亲节点的限制,也就是说看成父亲流到的流量为无穷),但是现在源点不一定为1,考虑怎么快速地"换根".设为为根时真正的答案.首先,它流到以为根时就是其儿子节点的流量是(注意是叶子节点时要赋为0).流到以为根时为父亲,而...

树形动态规划动态规划

2019-08-26

0 639

题解 | 算法竞赛进阶指南金字塔

思路设为字符串中从到部分为一整棵树时的方案数.我们可以枚举第一棵子树,也就是为一棵子树,其它子树在为剩余的子树(与为根节点,同时也是的根节点,也就是说这两个点是同一个点).然后乘法原理与加法原理计算出答案即可.可以发现,一般情况下,很多状态是无用的.所以用记忆化搜索效率更高. 代码 #includ...

动态规划区间动态规划

2019-08-25

1 617

题解 | 算法竞赛进阶指南清理班次

思路先将所有左边界-1,也就是将所有"块"变成"点",从"第l块到第r块"到"坐标之间的块",方便离散化.先对所有区间按右边界排序,枚举每个区间,更新答案大家可能发现我的转移方程与算法竞赛进阶指南上不太一样,因为我的表示方式不同,书上表示覆盖第1块到第i块都被覆盖过的最优答案,而我是坐标从到之间所...

线段树动态规划

2019-08-25

0 570

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

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

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

2019-08-25

0 603