浅谈dp优化之单调队列优化

《浅谈dp优化之单调队列优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浅谈DP优化之单调队列优化先来看一道简单题EOJ469MowingtheLawnFJ有N(1<=N<=100,000)只排成一排的奶牛，编号为1...N。每只奶牛的效率是不同的，奶牛i的效率为E_i(0<=E_i<=1,000,000,000)o靠近的奶牛们很熟悉，因此，如果EJ安排超过K(1<=K<=N)只连续的奶牛，那么，这些奶牛就会罢工去开派对。现在FJ需要你帮助计算可以得到的最大效率。题解：令dp[i]表示前i只奶牛的最大效率sum[il表示前i只奶牛的效率之和容易得到状态方程：dp[i]=max{dp[j-l]+sum[i]-s

2、um[j]}(i-k<=j<=i)显然这是O(NK)的算法那么如何将他降到O(N)呢？其实只要做一个简单的变换即可:dp[i]-sum[i]=max{dplj-l]-sum[j]}(i-k<=j<=i)于是，我们发现如果我们令Kfj]=dp[j-l]-sum[j]，贝!JK[i]=max{K[jl}(i-k<=j<=i)现在想象我们维护K是一个单调递减的队列，那么状态转移时我们只要取出K队列屮下标满足要求的队首元素即可，且每个K[i]只用入队一次出队一次那么时间复杂度就是O(N)啦!(由于要满足i-k<=j

3、列元素的下标)如果还没冇理解，可以看一段我很搓的代码，其实还是容易理解的；while(st<=ed&&L[st]

4、先看dd_engi的背九讲。Ps:看背九讲的时候我还不会单调队列，因为背九讲里有提到，我去看了下楼教主的男人八题，也看过集训队论文，总感觉一头雾水。直到暑假集训的时候,自己动手尝试切了几题之后菜渐渐明白过来。其实，很多知识都是一个循序渐进的过程，功夫到了，自然就明白了。对于第i种物品来说，已知体积V，价值w,数量k,那么可以按照当前枚举的体积j对v的余数把整个动规数组分成v份，以下是v=3的情况：j012345678.jmodv012012012我们可以把每一份分开处理，假设余数为d。编号j012345对应体积dd+vd+2*vd+3*v

5、d+4*vd+5*v现在看到分组以后，编号j可以从j-k到j-1中的任意一个编号转移而来(因为相邻的体积正好相差v),这看上去已经和区间最大值有点相似了。但是注意到由于体积不一样，显然体积大的价值也会大于等于体积小的，直接比较是没有意义的，所以还需要把价值修正到同一体积的基础上。比如都退化到d,也就是说用F[j*v+d]-j*w来代替原来的价值进入队列。对于物品i,伪代码如下12345678FORd:=0TOv-1//枚举余数，分开处理清空队列FORj:=0TO(C-d)divv//j枚举标号，对应体积为j*v+dINSERTj,F[j*

6、v+d]—j*w//插入队列IFA[L]L//如果队列的首元素已经失效B[L]+j*w^F[j*v+d]//取队列头更新ENDFORENDFOR己知单调队列的效率是O(n),那么加上单调队列优化以后的多次背包,效率就是O(CN)了。上面绿色的这段是我从别人blog里直接拷贝过来的，原始出处应该是09年徐持衡得《浅谈儿类竹包题》我觉得写得已经很明白了，如果觉得还不清楚的话，我们自己来推一遍还是和EOJ469一样我们先写出多重背包最原始的状态方程：dp[j]=max{dp[j-k氺v[i]]+k*w[i]}(l<=k

7、<=m[i])其中，dp[jl表示前i个物品占用j体积所能得到的最大价值，m[il为物品i的个数，v[i]为物品i的体职，w[i]为物品i的价值现在，我们修改方程如下：(各变量意义参照粗体字)=>dp[j*v+d]=max{dp[(j-k)*v+d]+k*w}(l<=k<=m[i])令kk=j-k=>dp[j*v+d]=max{dp[kk*v+d]+(j-kk)*w}(J-l<=kk<=j-m[i])=>dp[j*v+d]-j*w=max{dp[kk*v+d]-kk*w}得出单调队列K[j]=dp[j*v+d]-j*w给出几道多重背包题P

8、OJ1014POJ1276POJ1742(男人八题之一，另有方法可以水过)HDU1059(即POJ1014)总结：通过两道道例题，再加上一些练我们很快就能发现构造单调队列往往是通过观察朴素DP