[学习笔记] 浅析DP优化1

本文主要是介绍[学习笔记] 浅析DP优化1，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

简述

许多DP题，可能会在你得到正确有效的DP状态及转移后，要求你利用相关性质优化DP 我们一般称这种题为毒瘤！

另外，有可能你的DP没有什么优秀的性质而难以优化，为了得到易于优化的DP，不得不调整状态和转移

这些就是DP优化的学问了

这篇笔记总结2种DP优化：数据结构优化、决策单调性优化

其他DP优化请期待浅析DP优化2QAQ

数据结构优化

DP转移过程中有些状态和贡献能用数据结构维护并快速转移，看出来后直接上数据结构就行

重要的是要 看出来！

决策单调性优化

对于形如 \(f(l, r) = \min\{f(l, k) + f(k, r)\} + w(l, r)\) 的转移式（\(w(l, r)\)为\([l, r]\)区间产生的固定贡献）

如果暴力枚举决策点 \(k\) 进行转移，时间复杂度是 \(O(n ^ 3)\)的

但有时候，有些神奇的性质能帮我们将其优化成 \(O(n ^ 2)\)

设\(f(l,r)\)​的决策点为\(K(l,r)\)​，我们发现，当对于任意\(1 \leq l \leq r \leq n，w(l, r)\)​满足\(w(l-x,r) + w(l, r + y) \leq w(l, r) + w(l-x,r+y)\)​这样“交错小于包含”的不等式（我们称ta为四边形不等式）时，可以得到\(K(l,r-1) \leq K(l,r) \leq K(l+1,r)\)​​

证明比较难 反正我不会，有兴趣自行百度

借此性质，我们可以调整一下转移顺序，缩小决策点的枚举范围，从而使转移的时间复杂度变为 \(O(n ^ 2)\)

当然随题目变化，也会有很多不同的优化形式，但都是利用了相似的性质

很多时候，难以直接证明四边形不等式的成立，这时我们就要靠猜测和打表了awa

例题

（打√的是蒟蒻博主做过的QWQ）

AT2558 √

P1880 √

P4767 √

CF868F

这篇关于[学习笔记] 浅析DP优化1的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！