决策单调性 学习笔记

很早学长就讲了这个，但到现在才会/kk。

1.理论基础

我们发现有一种dp题，它的决策点有如下变化：

$\mathrm{1111122223446777\dots}$

是的，随着转移点的递增，决策点也在递增。

那么我们可以利用这样的性质优化DP，这也称作1D1D优化。

2.实现方式

重点全在这里

我们看到它的决策点，会联想到单调队列。

但是决策点是会影响到一段区间的，不止和它之后的节点有关。

这种情况下，我们就要牺牲单调队列 $O(1)$ 维护单调性的方式，采用 $O(\log n)$ 的二分。

也有人管这个叫单调二分栈。

具体来讲，是再维护一个数组 $k$，表示在队列里 $i$ 号位置的影响范围最晚是哪里的下一位。

也就是最早不能被 $i$ 所覆盖的位置。

转移时根据k的范围，再考虑用哪个点转移。

大体上就这么多，下面讲细节。先放代码。

for(int i=1;i<=n;i++)
{//k[i]表示在i这个节点作为决策点最晚可以扩展到哪里的下一位。
	while(hh<tt&&k[hh]<=i) ++hh;//(1)
	f[i]=get_ans(Q[hh],i);pre[i]=Q[hh];
	while(hh<tt&&find(Q[tt],i)<=k[tt-1]) --tt;//找到的i作为决策点的最优位置如果早于Q[tt]的，就弹掉(2)
	k[tt]=find(Q[tt],i);Q[++tt]=i;/(3)
}

(1)步，是更新步骤。找第一个能够涵盖 $i$ 位置的决策点。

由于 $k$ 维护的是下一位，所以是小于等于。

根据单调性，它一定是最优的。

接下来更新 $f(i)$，注意取最大/最小值对单调性的影响。

(2)步，通过二分找决策点。

具体来说是找到第一个 $i$ 优于队尾的位置。

如果它在尾后元素的 $k$ 之前，说明对位影响的区间已经全被 $i$ 覆盖掉了。

这样直接弹出就好了，因为它永远也不会再成为决策点了。

(3)步，我们找到了一个并没有被完全覆盖的队尾。

但是 $i$ 已经影响到了它的一部分区间，所以要更新队尾的 $k$ 值。

此时队尾第一个不能覆盖的点就是 $i$ 最优的第一个点。

最后把 $i$ 加入即可。

二分部分没什么好说的，注意要求的是最大还是最小来确定二分是大于还是小于。

int l=x,r=n+1;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(get_ans(x,mid)>=get_ans(y,mid)) r=mid;
		else l=mid+1;
	}

如上，这是找最小值。所以找到第一个 $f(y)<f(x)$ 的位置。

*3.理论依据

说白了就是为什么有单调性。

现在还不会qwq。