以下是铺垫
我在做一道题目时发现以下式子
f[i]=max(f[j]+(a[i]<a[j]))f[i]=max(f[j]+(a[i]<a[j])) f[i]=max(f[j]+(a[i]<a[j]))
e,可能数学上有点不标准,大概意思就是如果 a[i]<a[j]a[i]<a[j]a[i]<a[j] 就是 f[j]+1f[j]+1f[j]+1 否则是 f[j]+0f[j]+0f[j]+0
我的一开始的思路是拿两个队列维护,假设是 a,ba,ba,b 队列
在求解完后不是要将 iii 加入队列吗,可能会将 aaa 中某些元素删除,但注意到:由于转移式不是彻底拆开了,所以可能当前删除的元素在以后可能会更优
因此尝试思路:由于值只有 0,10,10,1 ,而且只要当前状态会影响以后的状态(以前的状态不会影响未来状态),因此如果加入的 新元素代价−旧元素代价>1新元素代价-旧元素代价>1新元素代价−旧元素代价>1 就要删除旧元素,反之存在 bbb 队列中
但显然的,面对这个值只有 0,10,10,1 的情况并不会,因为如果旧元素(差为1)更优,当且仅当在未来时他的变化值为 000 ,但由于新元素本来就
少 111 ,就算后面变化代价为 111 也仅能相等,因此存储旧元素是完全没有必要的
问题(如果没看懂,可以看铺垫(尽量看吧))
形如
f[i]=maxΔ∈{0,1,2}(f[j]+Δ)f[i] = \max_{\Delta \in \{0,1,2\}} (f[j] + \Delta) f[i]=Δ∈{0,1,2}max (f[j]+Δ)
式子
如果暴力单调队列优化,可以这么做:
由于 Δ\DeltaΔ 值域很小,可以稍微特判,大概思路如下:
在求解第 iii 步时,队列中元素可能不是最优,但可能在未来更优,因此可以拿另一个队列存起来(不用存所有的,例如代价差>2的就不用存)
当 Δ\DeltaΔ 的值域变大,就会导致队列中存储的元素变多,但我们可以尝试分类,就是 fff 值相同的存一起,可以加快访问?
我是蒟蒻,说错了不要骂我喵