介绍

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

讲解

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

$f(i)=\underset{j=1}{\overset{i-1}{\min }}f(j)+w_{j,i}$

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

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

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

$\forall i\le j,w_{i,j}+w_{i+1,j+1}\le w_{i+1,j}+w_{i,j+1}$

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

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

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

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

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

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

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