单调队列优化dp总结
总结
例题一的状态转移方程:$res = max_{1 \leq i \leq N} \lbrace s[i]-min_{i-M\leq j \leq i-1} \lbrace s[j] \rbrace \rbrace$
例题二的状态转移方程:$f[i][j] = max_{j-L_i \leq k \leq S_i-1} \lbrace f[i-1][k]+P_i\*(j-k) \rbrace$
例题三的状态转移方程:$f[i] = min_{0\leq j<i \&\& \sum_{k=j+1}^{i}~ A_k \leq M} \lbrace f[j]+max_{j+1\leq k \leq i} A_k \rbrace$
例题四的状态转移方程:$f[r+p\*V_i] = max_{p-C_i\leq k \leq p-1} \lbrace f[r+k\*V_i]+(p-k)\*W_i \rbrace$
综合以上四种状态转移方程,并且只关注它们的 “内层循环” “决策变量” 及其所在的维度,这些状态转移方程都可以大致归为如下形式(除第三个方程稍有不同):
$$f[i] = min_{L(i) \leq j \leq R(i)} \lbrace f[j]+val(i, j) \rbrace$$
上式所代表的问题覆盖范围广泛,是 dp 中一类非常基本、非常重要的模型,这种模型也被称为 1D/1D 动态规划。它是一个最优化问题,$L(i)$ 和 $R(i)$ 是关于变量 $i$ 的一次函数,限制决策 $j$ 的取值范围,并保证其上下界的变化具有单调性。$val(i, j)$ 是一个关于变量 $i$ 和 $j$ 的多项式函数,通常是决定我们采用何种优化策略的关键所在。
回想以上例题的解法,我们都把 $val(i, j)$ 分成了两部分,第一部分仅和 $i$ 有关,第二部分仅和 $j$ 有关,对于每个 $i$,无论采取哪个 $j$ 作为最优决策,第一部分的值都是相等的,可以在选出最优决策更新 $f[i]$ 时再进行计算、累加。而当 $i$ 发生变化时,第二部分的值不会发生变化,从而保证原来较优的决策,在 $i$ 改变后仍然较优,不会产生乱序的现象。因此,我们就可以在队列中维护第二部分的单调性,及时排除不可能的决策,让 dp 的算法得以高效进行。所以在上述模型中,多项式 $val(i, j)$ 的每一项仅与 $i$ 和 $j$ 中的一个有关,是使用单调队列优化的基本条件。