1D/1D动态规划

介绍

$1D/1D$动态规划，就是指状态数为$O(n)$，转移为$O(n)$的动态规划方程。一般的情况下求解的时间复杂度为 O ( n 2 ) O(n^2) O(n2)，但是，通过优化可以使时间复杂度降到$O(nlogn)$甚至$O(n)$。下面来讲一讲$1D/1D$动态规划中的决策单调性优化。

讲解

在做DP题的时候，我们经常会遇到形如这样的DP式：

f ( i ) = min ⁡ j = 1 i − 1 f ( j ) w j , i f(i)=\min\limits_{j=1}^{i-1}f(j) w_{j,i} f(i)=j=1mini−1f(j) wj,i

关于决策单调性，有一下这样一个性质：

设$k(i)$表示状态$i$取到最优值时的决策，则

$\forall i\le j,k(i)\le k(j)$当且仅当：

∀ i ≤ j , w i , j w i 1 , j 1 ≤ w i 1 , j w i , j 1 \forall i\leq j,w_{i,j} w_{i 1,j 1}\leq w_{i 1,j} w_{i,j 1} ∀i≤j,wi,j wi 1,j 1≤wi 1,j wi,j 1

其中有涉及到四边形不等式的知识，大家可以自行学习，这里不再赘述。

如果$w$数组满足这个性质，则我们可以用决策单调性优化来降低其时间复杂度。

首先，我们可以从性质入手。显然满足$k(i-1)\le k(i)$，所以在枚举$i$的时候，可以从$k(i-1)$开始枚举。虽然这样能减少枚举次数，但在最坏情况下，时间复杂的还是会达到 o ( n 2 ) o(n^2) o(n2)

怎么办呢？我们换一种角度思考。在每次求出一个$f(i)$时，可以考虑它能够更新的状态有哪些。即使中途更新后的决策有可能不是最优的，但整个过程结束后，最终的结果肯定是最优的。

因为满足单调性，$f(i)$能够更新的第一个状态到全部状态的最后一个状态这个区间内$f(i)$都能更新。所以，我们可以用栈来维护数据。栈中的每个元素保存一个决策能更新到的起始位置和终止位置。当插入一个新位置时从栈中最后一个元素扫描，如果新决策能更新栈尾的决策的起始点，则将栈尾的元素删除出栈；如果不能更新，则在栈尾元素的起始位置和终止位置中二分查找第一个点$t$，使该点能够被新决策更新。栈尾决策的终止点改为$t$前一个点，新元素的起始点为$t$，终止点为最后一个点。

于是，DP式求解的时间复杂度就从 O ( n 2 ) O(n^2) O(n2)优化到了$O(nlogn)$

例题[HNOI2008]玩具装箱（附题解）

这篇好文章是转载于：学新通技术网