DP - Monotone Queue

用单调性优化动态规划.doc

https://blog.csdn.net/A1847225889/article/details/77777009
什么类型的DP需要用到常规的单调队列？
类似这样的转移方程可以用到单调队列：
f[i]=max(g[j])+w[i]
f[i]=max(g[j])+w[i]

其中，g[j]是一个与i无关系的数。w[i]只与i有关系。
怎么用？
我们首先开一个队列。DP时：
1、先删掉前面超出范围的队头。
2、利用队头转移。
3、将这个数和队尾比较，若队尾不比它优，就删掉队尾，直到队列为空或队尾比它优。最后将它加进队尾。

原因
1、单调队列中的数都在要范围之内。
2、队头最优（不然早被后面的删掉了）。
3、为什么不只存队头？因为队头比较老，若超出范围就要被删掉。

https://blog.csdn.net/er111er/article/details/78344161
那么单调队列有什么用呢？优化DP。许多单调队列优化的DP可以使复杂度直接降维

关于单调队列的运用还有很多，例如斜率优化DP等等。总而言之，使用单调队列优化DP，那么必会有求i之前某个范围的极值的操作，这类DP的方程通常为：
F[i]=min(F[j]+a[i]:j<i)F[i]=min(F[j]+a[i]:j<i)
a[i]是与j无关的数。

https://blog.csdn.net/fish_porridge/article/details/47778887
单调队列：是在一个队列中选出的一些元素构成的队列

正因为单调队列能够将一些无用的店删去并且保持了第一个数就是最值

所以我们可以将一些求么某个区间的最值转化成单调队列来做


单调队列优化：

嗯 不知道从哪里盗来的图(很感谢原作者)

这张图能很好的说说明在什么样的情况下去优化

对于图中的dp[i][j]他可以由f[i-1][j-c]到d[i-1][j-1]某一个最值，这里假设最大值；

那么在对于下一个数dp[i][j+1] 他的区间只是往后推了 所以有部分区间是重复的 可以将重复区间进行记录，这个正好是单调队列所拥有的性质

好了回到这倒题本身，这个题是说我们经行股票的买卖，但是我们的每一次的交易与上一次的交易的时间差是不能小于w

求最大获利

嗯 我们可以很快速的想到这道题的dp方程为 dp[i][j]=max{dp[i-1][j](不进行买卖)，dp[i-w-1][k]-(j-k)*a[i],dp[i-w-1][k]+(k-j)*b[i]};

很显然这个是n三次转移方程

但是我们对于产生第三个n进行优化，将我们得到的式子进行化简，所以dp[i][j]=dp[i-w-1][k]+k*a[i]-j*a[j]，其实我们就是对于每一个i,j求dp[i-w-1][k]+k*a[i]的最大值

所以我们可是令f[i][k]=dp[i-w-1][k]+k*a[i]

对于卖出也是同买入的情况