算法合集之《从一类单调性问题看算法的优化》.ppt

《算法合集之《从一类单调性问题看算法的优化》.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、从一类单调性问题看算法的优化长沙市一中汤泽充分挖掘数据关系,灵活运用数据结构,往往是构造出优秀算法的关键因素一般队列:一端插入,另一端删除特殊队列:尾端插入,两端删除单调性:帮助优化一类单调性问题问题1锯木厂选址2<=N<=20000,1<=Wi<=10000,1<=Di<=10000123112112131261213W:N=9D:问题1锯木厂选址最优方案中,锯木厂必定建在有树的位置问题1锯木厂选址123112112131261213W:N=9D:123112112131261213W:N=9D:0012345678910Sd02367915161819

2、Sw1367101113141515问题1锯木厂选址分析:C[I]:在第I棵树处建立一个锯木厂,并且将第1到第I棵树全部运到这个锯木厂所需的费用W[J,I]:在第I棵树处建立一个锯木厂,并且将第J+1到第I棵树全部运往这个锯木厂的费用问题1锯木厂选址分析:F[I]表示在第I棵树处建立第二个锯木厂的最小费用,则:这个算法的时间复杂度为O(N^2)问题1锯木厂选址IJI+1J问题1锯木厂选址证明:令S[K,I]表示决策变量取K时F[I]的值设K1

3、<0令g[K1,K2]=上面不等式的左边因为D[K]≥0,因此Sd序列不下降因此决策是单调的!问题1锯木厂选址分析:维护一个特殊队列K,K1g[Kn,I],Sd[I’]>g[Kn-1,Kn]>g[Kn,I]Kn比Kn-1优之前I就将比Kn优,删除Kn,重复该步骤,最后将I

4、插入队列算法总复杂度O(N)问题2旅行问题问题描述:一个环形跑道上有n个加油站，按顺时针编号为1到n(3

5、[5]=5;D[5]=4S=3S=3S=6S=4S=8S=2S=1S=4S=3S=4以1号加油站为起点问题2旅行问题一个例子:N=5P[1]=3;D[1]=1P[2]=1;D[2]=2P[3]=5;D[3]=2P[4]=0;D[4]=1P[5]=5;D[5]=4S=1以2号加油站为起点S=-1问题2旅行问题一个例子:N=5P[1]=3;D[1]=1P[2]=1;D[2]=2P[3]=5;D[3]=2P[4]=0;D[4]=1P[5]=5;D[5]=4S=1S=0S=-1以2号加油站为起点S=3问题2旅行问题一个例子:N=5P[1]=3;D[1]=1P[2]

6、=1;D[2]=2P[3]=5;D[3]=2P[4]=0;D[4]=1P[5]=5;D[5]=4以1、3、5号加油站为起点有办法周游一圈算法一分析:直接模拟刚刚的演算过程总的时间复杂度为O(N^2)但是N最大可以达到10^6!太慢了!算法二分析:假定只能按顺时针方向行驶.令A[I]=P[I]-D[I]A[I+N]=A[I]A[0]=0设SA[I]表示A序列中前I项的和算法二0123456789A02-13-112-13-1sa021434658712345P31505D12214算法二分析:SA[I]到SA[I+N-1]都不小于SA[I-1]SA[I]到S

7、A[I+N-1]中的最小数不小于SA[I-1]求N个数中的最小数,很自然地想到了堆!算法二0123456A02-13-112Sa021434612434134413464堆中不超过N个元素2N次插入操作2N次删除操作N次取堆顶元素总复杂度O(NLog2N)算法三分析:给定一个序列SA和N个区间求出每个区间中的最小值,对其作相应判定这是一个标准的RMQ问题!时间复杂度降为O(N)SA:0214342143算法四分析:给定的N个区间不存在包含关系,满足单调性!0123456789Sa:0214342143K:22777同样满足单调性?算法四预处理:维护一个特殊

8、队列K,K1