dp的单调队列优化

dp的单调队列优化

解题流程

适用于状态转移方程中含有区间最值操作的优化方法，只要能够快速得求出一段区间的最值，那么就可以快速得尽兴状态转移，然后就可以达到优化dp状态转移时产生的时间复杂度。众所周知，单调队列可以$O(1)$求解区间最值问题，那么通过单调队列维护dp值就可以将原本状态转移时的时间复杂度从$O(n)$降低至$O(1)$。

多重背包的单调队列优化

易得一般形式中的状态转移方程为$dp[i][j]=max(dp[i-1][j-wi*k]+k*vi)$ $(0<=k<=ki)$

通过枚举每一个物品不能刚好放下的剩余空间,将$dp[i][j]$化成$g[x][y]=dp[i][x*wi+y]$ ,$g'[x][y]=dp[i-1][x*wi+y]$,通过枚举每一个$y$来枚举所有的状态。然后通过令$G[x][y] =g'[x][y+x*wi]-wi*x$来消去状态转移方程中的$k$。

然后就有状态转移方程$g[x][y]=max(G[x-k][y])+vi*x$这样就可以用单调队列来维护$G[x-k][y]$就可以将$g[x][y]$在$O(1)$的时间内转移出来，然后就把复杂度从$O(n*m^2)$转移到了$O(n*
m) $。

例题:1. P1776宝物筛选