首页 > 其他分享 >DP 技巧总结

DP 技巧总结

时间:2024-11-11 19:29:35浏览次数:5  
标签:总结 状态 技巧 可以 插入 答案 转移 DP

DP 技巧总结

进行了为期接近一周的 DP 特训,做了很多同学找的高质量题目,也学到了很多技巧。现在来把一些感觉比较有价值的技巧进行一些统一的总结。

插入型 DP

这个东西之前应该在选拔期间的一场周测中见过,但是隔了很久,已经有所遗忘。这次题单里出现了两道类似的题目,我都不会做。其实插入型 DP 是一种套路,没见过的话很难自己独立做出来,但只要见过几次后就会感觉好很多。
其实感觉插入型 DP 主要解决的是对于序列中的不重复元素进行转移,比如满足条件的排列等等。主要的思路就是设一个状态 \(f_{i,\cdots}\) 表示已经插入前 \(i\) 个数的情况下的答案,然后对于一个新进来的元素 \(i\),在基于已经插入前 \(i-1\) 个数的基础上,将 \(i\) 插入到序列中的每个位置,使其能满足题目条件(即 \(f_{i,\cdots} \leftarrow f_{i-1,\cdots}\))。许多要求元素两两不同的题目在其他状态无法转移的情况下都可以尝试这种设法,可以做到不重不漏(很多其他状态都可能会重或漏)。还有一类基于插入型 DP 的题目,可以设 \(f_{i,j}\) 表示插入了前 \(i\) 个数后形成了 \(j\) 个组的答案,然后通过三种转移:新开一个组、插入一个组、合并两个组,来从 \(i-1\) 转移到 \(i\),比如特训中的 A 题就是这种类型,其本质就是对一个类似山峰的东西进行 DP,要求两个元素中必有一个山峰,而且固定起点,并限制为一个排列,这种情况下就可以使用这种状态进行分组。

结合二分

这个东西也遇到过几次,比如之前模拟赛的二分 + 背包,还有这次特训的 B。当有时候答案不好直接 DP,并且答案满足单调性时,可以考虑二分答案,然后 check 中一般是最优性问题,可以考虑 DP。

(怎么感觉我在对每一道题进行总结)

DP 一条链

有时候一些树上问题最终的答案形态是一条链,这时候一般有两种思考方法。我原先一般都是用的先随便钦定一个根,然后对于一条路径 \((u,v)\),将它的答案放到 LCA 处处理(相当于在 LCA 处合并两条不同的以 LCA 为最深点的向下的链),然后可以设状态 \(f_{i,\cdots}\) 表示以 \(i\) 为根、向下的链的答案。在对 \(u\) 进行 DP 时,对于一条边 \((u,v)\),先合并之前的边,再用之前合并的状态来和 \(v\) 合并,即用之前的 \(f_{u,\cdots}\) 与 \(f_{v,\cdots}\) 合并。然后其实还有一种做法,就是对于每个点,钦定它为根,然后 DP 一条单链,这样可以保证考虑到了每种情况。但是使用这种方法有几个前提,比如从父亲到自己,答案的修改不能太复杂,答案要易于合并,修改答案的时间复杂度不能太高……总之,换根 DP 可能有时候稍显麻烦,而且一般细节比较多,所以我不是很喜欢。

优化状态

其实优化状态不仅指将状态降维,还可以将状态所表示的量进行一些修改,使得更好转移。这种题一般要具体问题具体分析。比如特训中的 D,本来是设的 \(f_i\) 表示前 \(i\) 盏灯笼是否可以被覆盖完,但是会发现这种状态并不好转移,所以可以考虑增加一下状态所含的信息,\(f_i\) 表示在能完全覆盖的情况下,前 \(i\) 盏灯笼能覆盖到的最远位置,然后转移就比较简单了。当然可以考虑将状态降维,排除一些冗余的状态,比如 F,本来是设的 \(f_{i,j}\) 表示 \(a,b\) 序列分别 DP 到 \(i,j\) 的答案,但是这种状态显然不能通过,我们考虑到其实很多状态都是冗余的,比如 \(a,b\) 两个序列单独选的情况,其实并不需要将其放到一起考虑,可以分开算,所以说我们可以将状态减省为 \(f_i\),这样就在保证答案正确的基础上排除了大量冗余状态。

优化时间

当状态已经不能够精简,并且时间复杂度难以通过时,可以观察转移的形式,考虑优化转移。策略比较多,需视情况而定,比如使用数据结构优化(如 I,典型的单调队列优化)、观察决策点的性质(如 G,决策单调性),或者直接用简单方法也行。需要注意的是在时间复杂度均能通过的前提下,能使用简单的方法优化就用简单的方法,不要用复杂的东西(比如能用树状数组就不要用线段树),这样可以减少大量的代码复杂度与调试时间。

容斥

有些计数题,总是会算到一些重复的方案,这时候可以用到容斥。这类题一般比较难,所以放一道具体的题进行分析。

例如特训中的 H,可以考虑对于不同的颜色来进行 DP,而不是对序列中的每个元素进行 DP。然后就可以将问题转化为求 \(m\) 种颜色,恰好 \(0\) 个位置上的颜色与原来相同的方案数。但是可以发现“恰好”的方案数不太好算,所以考虑使用一种套路,用“至少”来容斥出“恰好”。设 \(f_{i,j}\) 表示前 \(i\) 种颜色,至少 \(j\) 个位置与原来位置上的颜色相同,不考虑剩下的元素的方案数。转移考虑新添加一种颜色,选取一些相同颜色进行交换,转移即为 \(f_{i,j} = \sum\limits_{k=0}^{\min(j,cnt_i)} f_{i-1,j-k} \times \binom{cnt_i}{k} \times A_{cnt_i}^{k}\)。最后考虑容斥,使用“奇减偶加”的原则计算答案,并把剩下的元素进行一个统一的排列,即 \(ans = \sum\limits_{i=0}^{n} (-1)^i (n-i)! f_{m,i}\)。解释一下这样做的原理:

对于恰好 \(i\) 个元素的值与原来相同的情况,他会被每一个至少 \(j \thinspace (j \leq i )\) 个元素与原来的相同的情况计算到,算到的次数相当于从 \(i\) 个位置中选取 \(j\) 个作为那些“至少”,所以对于每一个 \(j\) 都会产生 \(\binom{i}{j}\) 次的贡献。由于我们想让恰好 \(i=0\) 的情况被算到恰好 \(1\) 次,而恰好 \(i>0\) 的情况被算到恰好 \(0\) 次。由于我们采用了“奇减偶加”的方法,所以对于每一个恰好 \(i\) 的情况,会被算到的次数为:

\[\sum\limits_{j=0}^{i} (-1)^j \binom{i}{j} = \sum\limits_{j=0}^{i} (-1)^j 1^{i-j} \binom{i}{j} = \left\{ \begin{matrix} 1 \thinspace (i=1) \\ 0 \thinspace (i>1) \end{matrix} \right. \]

这正好符合我们的要求,所以这样做是正确的,可以不重不漏的统计到每种方案。

其实容斥所包含的还远远不止这些,还有诸如 \(O(2^n)\) 的枚举所有情况、DP 不合法方案数最后再减去等等许多的类型,所以这只是容斥的冰山一角,以后还要靠多练习来更熟练的掌握每种方法。当然计数不要老是只想着容斥,有时可以换一换方向,

观察性质

其实感觉后期的题很多时候直接上来就 DP 是远远不够的,有时还要基于一些观察得到的性质再 DP。比如特训中的 J,其实最终每个连续子段的 \(MEX\) 都必须等于原序列的 \(MEX\),证明也比较简单,最后每个连续子段的 \(MEX\) 都相等,说明最终的 \(MEX\) 在每个子段中都没有出现,而且是最小的那个,最终就是原序列的 \(MEX\)。还有比如之前模拟赛有道题叫边境探照灯,一个重要性质就是每个探照灯要么高度为 \(0\),要么高度为它能达到的最高高度,基于这一点就可以进行 DP 了,最后使用数据结构优化即可。还有其他一些各种奇怪的东西,比如基于部分策略贪心的正确性进行 DP 等。这个东西还是比较灵活,并且省选/NOI 经常也会考这种东西,还是见多识广并灵活运用之后才能较快解决这种问题。

总结

DP 这种算法在信息学竞赛中的重要性不言而喻,不说占领了半壁江山,起码也有 \(\frac{1}{4} \sim \frac{1}{3}\)。感觉这一年以来自己的 DP 水平虽然还是很拉,但至少还是有很大提升,从去年的对 DP 一窍不通、遇到就栽,到现在的能够独立做出一些有难度的 DP 题,还是有许多收获的。其实感觉很多情况下做不出来 DP 题很大程度上是因为自己不会设状态,少数情况下是不会转移。所以 DP 这个东西还是比较吃灵感和天赋的(当然我两个都没有)。希望自己之后的 DP 水平能够继续提升,上一个新台阶。

标签:总结,状态,技巧,可以,插入,答案,转移,DP
From: https://www.cnblogs.com/gevenfeng/p/18540414

相关文章

  • 迟来的2023秋招总结,互联网&银行&国企&腾讯
    复制自本人知乎首先现在是2023年四月中旬,毕业的事情暂时告一段落,于是想吐槽顺便记录一下。23秋招其实是在2022年,而2022实在是这几年来行情最差的一年。犹记得20、21年秋天各个大厂号称“史上最大规模的秋招“,hc多开的薪资也高,一年比一年倒挂。当时我还觉得23年会更美好,没想到现......
  • 渗透测试中登录框骚操作总结(非常详细)零基础入门到精通,收藏这一篇就够了
    由于测试过程中很多系统我们能接触到的只有一个登陆界面,所以要充分挖掘漏洞,进行深入操作登录注册万能密码绕过登录存在SQL注入的情况下,有可能使用万能密码直接登录admin'or'1'='1'--``admin'OR4=4/*``"or"a"="a``'or''='``'or1=1--有超级多登录口SQL......
  • 《IDEA 使用技巧分享》
    一、引言在当今的软件开发领域,集成开发环境(IDE)的选择对于开发者的效率和代码质量起着至关重要的作用。IntelliJIDEA作为一款功能强大、广受好评的Java集成开发环境,拥有众多实用的功能和技巧,可以极大地提高开发效率。本文将详细介绍IDEA的一些使用技巧,帮助开发者更好地......
  • 20万字208道Java经典面试题总结(附答案)
    1、JDK和JRE有什么区别?JDK(JavaDevelopmentKit),Java开发工具包JRE(JavaRuntime Environment),Java运行环境JDK中包含JRE,JDK中有一个名为jre的目录,里面包含两个文件夹bin和lib,bin就是JVM,lib就是JVM工作所需要的类库。2、==和 equals 的区别是什么?对于基本类型,==比较的......
  • # 学期(如2024-2025-1) 学号(如:20241402) 《计算机基础与程序设计》第8周学习总结
    学期(如2024-2025-1)学号(如:20241402)《计算机基础与程序设计》第8周学习总结作业信息这个作业属于哪个课程<班级的链接>(如2024-2025-1-计算机基础与程序设计)这个作业要求在哪里<作业要求的链接>(如2024-2025-1计算机基础与程序设计第一周作业)这个作业的目标<写上......
  • 利用 Linux 系统性能调优技巧优化系统性能
    ......
  • JavaScript基础总结
             JavaScript(简称JS)是一个广泛使用的客户端脚本语言,常用于网页开发中。它可以在浏览器中运行,执行交互操作和动态效果。以下是JavaScript基础的所有核心知识点,按主题分类列出。1.基本语法声明变量使用var、let和const来声明变量:varname='Alice';/......
  • MYSQL事务学习总结
    前言在数据库操作的复杂世界里,事务是保障数据一致性、完整性和可靠性的关键机制。无论是银行系统中的资金转账,还是电商平台的订单处理,事务都在默默地发挥着重要作用。MySQL作为广泛使用的数据库管理系统,其事务处理机制涉及到多个重要的概念和特性。从原子性确保操作的整体性......
  • 二维数点总结
    有很多数数题都可以转化为二维数点模型。将一些二元信息视作平面上的若干个点,查询即数一个矩形中有多少个点/点的权值之和等信息。那么这很明显是DS题(或者至少要上DS优化一下)。我们来想想怎么处理矩阵查询。离线离线的时候做法很多。但基本都有一个共性:把询问差分,转化为前缀信......
  • Python爬虫快速获取JD商品详情:代码示例与技巧解析
    在当今这个信息爆炸的时代,数据成为了一种宝贵的资源。对于电商行业来说,获取商品详情信息是进行市场分析、价格比较、库存管理等重要环节的基础。本文将通过一个Python爬虫示例,展示如何快速获取(JD)商品的详情信息。为什么选择Python进行爬虫开发?Python作为一种高级编程语言,以......