在去年银川站的比赛中，我们就因为一道四边形不等式优化动态规划的题目与金牌失之交臂。四边形不等式作为动态规划的常用优化技巧，在竞赛中运用极多。下面就让我们一起来学习这个神奇的技巧吧！ [NC 51244] Post office 题目描述 在一个一维坐标轴上有 $v(1 \le v \le 300)$ 个村庄，要建 $p(1 \le p \le 30)$ 个邮局，每个邮局都在村庄上。每个村...
在之前的BLOG里，我们对几种主流的动态规划类型和常用的动态规划优化思路进行了讲解。而从这一篇开始，我们就要开始学习一些更加固定的技巧性的东西了。这篇BLOG就让我们从熟悉的单调队列出发，学习非常常用的斜率优化这一技巧吧！ 单调队列 单调队列-滑动窗口 题目描述 给定一个长度为 $n$ 的数列，求长度为 $k$ 的定长连续子区间 $(a_1, a_2, \dots, a_k)$，$(a_...
一提到动态规划的优化，你第一反应想到的是什么？是斜率优化还是四边形不等式，亦或是各种加速转移的辅助数据结构。动态规划作为运筹学的一个重要部分，其本质是数学的是美的。我们除了这些技巧性的方法，还可以尝试从动态规划本身性质入手进行优化。下面就让我们来一同了解动态规划的常见优化思路。 经典例题 说到动态规划的优化，就不得不提到一篇非常经典的国家集训队论文—《优化，再优化！——从<鹰蛋&g...
相信树形动态规划大家都已经很熟悉了，不熟悉的同学可以点击链接进行巩固复习。而在树形动态规划之上，还有一种 “PLUS树形” 动态规划，也就是我们接下来要提到的基环树动态规划，这种动态规划一经出现就席卷了各大平台。下面就让我们一同看看吧。 基环树 在图论中，树被视作为一种特殊的图 $G=(V, E)$，其中$|V| = |E|+1$。其存在如下特性： 树 $G$ 上任意两点必定能够通过途...
在 $NOI2009$ 的赛场上，一道叫《管道取珠》的题目横空出世，以及新颖的解法和独到的思维方法被誉为“人类智慧的结晶”。在之后对这道题的模仿、改编甚至加强一直都没有停下过。不得不承认管道取珠一类问题在 $2021$ 年的今天已经变成非常经典的一类问题了。今天我就结合管道取珠原题和一道 $ICPC$ 区域赛的题目，浅谈一下管道取珠这一类问题的思考方法。 原滋原味[管道取珠] 题目描述 ...