louhc

题解

未归档(78)

/ 注册

全部文章 / 题解（共2篇）

题解 | 算法竞赛进阶指南 Polygon

思路很明显的区间DP.环形处理可以使用枚举断哪条边(复杂度为,比较危险)或者复制一遍接在后面(复杂度为).这里采用后者.转移时乘法需要注意负数,因为负负得正可能反而比两个最大值相乘更大,因此需要同时记录区间能得到的最大值和最小值.加法转移:乘法转移:然后在取最大值即可. 代码 #include&l...

动态规划区间动态规划

2019-08-27

0 784

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

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

动态规划区间动态规划

2019-08-25

1 617