在 $NOI2009$ 的赛场上，一道叫《管道取珠》的题目横空出世，以及新颖的解法和独到的思维方法被誉为“人类智慧的结晶”。在之后对这道题的模仿、改编甚至加强一直都没有停下过。不得不承认管道取珠一类问题在 $2021$ 年的今天已经变成非常经典的一类问题了。今天我就结合管道取珠原题和一道 $ICPC$ 区域赛的题目，浅谈一下管道取珠这一类问题的思考方法。 原滋原味[管道取珠] 题目描述 ...
概率是我们日常生活中随处可见的东西，但就是这么一个平常看起来平易近人的东西在遇上动态规划组合成概率$DP$的时候，就往往会让人血压升高抓耳挠腮。这篇$BLOG$，我将和你一起窥探概率$DP$的冰山一角，大致了解其解题思路和应对方法。 概率动态规划 要了解概率动态规划也就是概率$DP$，我们要先了解一下什么是概率。所谓概率就是反映随机事件出现的可能性大小的量度比如掷骰子出 $6$ 点的概率...
前段时间一位许久未见的小伙伴去做米哈游的面试题被数位动态规划裸题打倒了……为了帮助他走出阴霾也为了延续我们的动态规划系列，数位$DP$它终于来了。没有接触的同学也不要害怕，这一篇尽可能给你带来一篇保姆级的教学。 数位动态规划 数位$DP$是一种计数用的$DP$，一般就是要统计一个区间 $[l,r]$ 内满足一些条件数的个数。所谓数位 $DP$，我们从字面意思理解就是在数位上也就是十进制下...
说到进阶的动态规划，怎么能少了状态压缩动态规划（状压$DP$）呢。我们之前提到过，动态规划就和恋爱一般，一定要将自己的信息包括历史遗留问题交代清楚。但总是有问题很多信息很多的人存在的，我们状压DP就是用来解决这类问题的。 状态压缩动态规划 状压$DP$ 是动态规划的一种通过将状态压缩为整数来达到优化转移的目的的动态规划方法。在进行状压$DP$的时候，我们要把所有的压缩状态都看成是 $01...
在之前的动态规划专题BLOG中，我们已经学会了简单的线性动态规划啦。从这篇BLOG开始，我们就正式进入动态规划的进阶篇啦，作为进阶动态规划的第一篇BLOG，我们还是得一同学习一下我们的老朋友——树形动态规划。 树形动态规划 在学习树形动态规划之前，我们先要搞清楚一个问题，什么是树？根据图论课上学到的知识我们知道，连通的无圈图称为树。而树我们可以把它近似第看成一个分形结构，这是说我们的树其...