《一类单调问题的求解【谷风课资】.ppt》由会员分享，可在线阅读，更多相关《一类单调问题的求解【谷风课资】.ppt（49页珍藏版）》请在三一文库上搜索。
1、一类单调问题的求解,中山纪念中学 宋新波,1,一类课资,例0.老徐真人秀,day1,80,day2,75,day3,78,day4,73,day5,79,80,80,7875，既新鲜又美味,80,80,7973,7978,day5-day1=4天,79,2,一类课资,一.单调队列及应用,3,一类课资,一.单调队列及应用,4,一类课资,例1.NOIP2010初赛烽火传递,5,一类课资,例1.NOIP2010初赛烽火传递,6,一类课资,例2.GDKOI2009猴子,7,一类课资,例2.GDKOI2009猴子,8,一类课资,例3.多重背包,9,一类课资,例3.多重背包,10,一类课资,例3.多重背包
2、,11,一类课资,例4.HNOI2008Toy,12,一类课资,例4.HNOI2008Toy,13,一类课资,例4.HNOI2008Toy,14,一类课资,例4.HNOI2008Toy,15,一类课资,例4.HNOI2008Toy,16,一类课资,例4.HNOI2008Toy,17,一类课资,例4.HNOI2008Toy,j1,j2,j3,j4,j5,T(j3,j4)T(j4,j5),T(j2,j3)T(j3,j5),T(j1,j2)2g(i),最优决策为j2,18,一类课资,例4.HNOI2008Toy,19,一类课资,例5.APIO2010特别行动队,20,一类课资,例5.APIO2010
3、特别行动队,21,一类课资,例5.APIO2010特别行动队,22,一类课资,例5.APIO2010特别行动队,23,一类课资,例5.APIO2010特别行动队,24,一类课资,例5.APIO2010特别行动队,25,一类课资,二.斜率优化总结,26,一类课资,二.斜率优化总结,27,一类课资,三.斜率优化,28,一类课资,例6.游戏,29,一类课资,例6.游戏,30,一类课资,例6.游戏,31,一类课资,例6.游戏,32,一类课资,例6.游戏,33,一类课资,四.斜率优化,34,一类课资,例7.NOI2007货币兑换,35,一类课资,例7.NOI2007货币兑换,36,一类课资,例7.NOI
4、2007货币兑换,37,一类课资,例7.NOI2007货币兑换,38,一类课资,例7.NOI2007货币兑换,39,一类课资,例7.NOI2007货币兑换,40,一类课资,例7.NOI2007货币兑换,j1,j2,j3,j4,j5,j6,j7,T(j2,j3)T(j3,j7),T(j7,j4)T(j4,j5),T(j7,j5)T(j5,j6),41,一类课资,例7.NOI2007货币兑换,42,一类课资,例7.NOI2007货币兑换,43,一类课资,例7.NOI2007货币兑换,44,一类课资,例7.NOI2007货币兑换,45,一类课资,例7.NOI2007货币兑换,46,一类课资,例7.NOI2007货币兑换,47,一类课资,五.斜率优化,48,一类课资,六、总结,49,一类课资,