dp的斜率优化

dp的斜率优化

斜率优化

单调队列优化的一种延伸 通过使用了数形结合的思想，使用一次函数将状态转移的复杂度转化至$o(1)$。

做题步骤：

1.列出状态转移方程

列出形如$dp(i)=max(dp(j)+A(i)*B(j)+C(j)+D(i))$的状态转移方程。

2.考虑如何删去队头

然后通过假设单调性，假设j<k且k转移到i的方案比j转移到i的方案更加优秀。

然后进行公式化简，得到Y(k)-Y(j)/X(k)-X(j)> K(i)的公式，这样就可以通过计算队头两点的斜率来判断是不是要让队头元素出队。

3.状态转移

因为在队列中已经求出合法的情况，那么最优的转移方式就是取队头。

4.考虑如何加入新决策！

令solve(i,j)=(Y(i)-Y(j))/(x(i)-x(j))
假设有 j<k<p且solve(j,k) > solve(k,p)

if( solve(k,p)<k(i))那么p的决策要优于k

if(solve(k,p)>=k(i))那么solve(j,k)>k(i))也就是说明了k不比j优秀！

结合两个if，得出 j<k<p且solve(j,k) > solve(k,p)时k就出队！

那么k就要出队！所以只要满足solve(j,k)>solve(k,p)k就要出队！