分类: 动态规划

5 篇文章

HDU 6406 Taotao Picks Apples 杭电多校第八场
题意 略 题解 由于这是一个不用维护原有序列的操作,我们可以考虑维护一个ST表进行RMQ查询。 这个RMQ是用来干什么呢? 根据题目数据范围,我们知道这道题不能容忍$\mathcal O(n^2)$及以上的算法 我们必须要在$\mathcal O(nlogn)$的时间复杂度下完成所有的操作。 维护一个dp数组,$dp[cur] = dp[first…
HDU 6356 Glad You Came Problem 1007 杭电多校第五场
题意 给定长为$n$的数组,初始值均为0 执行m个操作,每次操作的行为 如原题面 题解 很多人用线段树弄过去了,但是这个非常考验模板的水平,如果常数比较大这个方法就GG了 官方题解的解法说的不是很清楚,而根据官方标程的实现方式,实际上就是一个标准的RMQ逆向的过程。 首先对于RMQ 我们要学习什么是ST表。附录:ST表 然后我们在m次操作中,把一个…
UPC6360 词韵 2018北京冬令营
题目描述 Adrian 很喜欢诗歌中的韵。他认为,两个单词押韵当且仅当它们的最长公共 后缀的长度至少是其中较长单词的长度减一。也就是说,单词 A 与单词 B 押韵 当且仅当 LCS(A, B) ≥ max(|A|, |B|) – 1。(其中 LCS 是最长公共后缀 longest common suffix 的缩写) 现在,Adrian 得到了 N…
关于使用Floyd解决最短路问题的一些注意事项
根据Floyd算法我们可以通过状态转移方程解决一个无向图或者有向图中两点之间最短路径的问题,其时间复杂度为O(n³),空间复杂度可以控制在O(n²)(一般情况)。但是在实际运用中如果对Floyd三重循环的ijk顺序有改动,会导致无法正确得出两点之间的最短路径的问题。 正确的做法是   [code lang="cpp"] for(int k…