2.一类单调问题的求解(宋新波1.28下午)课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,WC2016绵阳南山,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,WC2016绵阳南山,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,WC2016绵阳南山,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,WC2016绵阳南山,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,WC2016绵阳南山,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,WC2016绵阳南山,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,WC2016绵阳南山,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,WC2016绵阳南山,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,WC2016绵阳南山,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,WC2016绵阳南山,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,WC2016绵阳南山,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,WC2016绵阳南山,*,一类单调问题的求解,中山纪念中学 宋新波,1,WC2016绵阳南山,例,0.,老徐真人秀,WC2016绵阳南山,2,day1,80,day2,75,day3,78,day4,73,day5,79,80,80,7875,，既新鲜又美味,80,80,7973,7978,day5-day1=4,天,79,一,.,单调队列及应用,3,WC2016绵阳南山,一,.,单调队列及应用,4,WC2016绵阳南山,例,1.NOIP2010,初赛,烽火传递,5,WC2016绵阳南山,例,1.NOIP2010,初赛,烽火传递,6,WC2016绵阳南山,例,2.GDKOI2009,猴子,7,WC2016绵阳南山,例,2.GDKOI2009,猴子,8,WC2016绵阳南山,i,j-1,j,例,3.,多重背包,9,WC2016绵阳南山,例,3.,多重背包,10,WC2016绵阳南山,i,j,i-1,j-v,i,j+v,i,例,3.,多重背包,11,WC2016绵阳南山,例,4.HNOI2008Toy,12,WC2016绵阳南山,例,4.HNOI2008Toy,13,WC2016绵阳南山,例,4.HNOI2008Toy,14,WC2016绵阳南山,例,4.HNOI2008Toy,15,WC2016绵阳南山,例,4.HNOI2008Toy,16,WC2016绵阳南山,j1,j2,j3,例,4.HNOI2008Toy,17,WC2016绵阳南山,例,4.HNOI2008Toy,18,WC2016绵阳南山,j,1,j,2,j,3,j,4,j,5,T(j3,j4)T(j4,j5),T(j2,j3)T(j3,j5),T(j1,j2)2g(i),最优决策为,j2,例,4.HNOI2008Toy,19,WC2016绵阳南山,例,5.APIO2010,特别行动队,20,WC2016绵阳南山,例,5.APIO2010,特别行动队,21,WC2016绵阳南山,例,5.APIO2010,特别行动队,22,WC2016绵阳南山,例,5.APIO2010,特别行动队,23,WC2016绵阳南山,例,5.APIO2010,特别行动队,24,WC2016绵阳南山,例,5.APIO2010,特别行动队,25,WC2016绵阳南山,二,.,斜率优化总结,WC2016绵阳南山,26,二,.,斜率优化总结,WC2016绵阳南山,27,三,.,斜率优化,WC2016绵阳南山,28,例,6.,游戏,WC2016绵阳南山,29,例,6.,游戏,WC2016绵阳南山,30,例,6.,游戏,WC2016绵阳南山,31,例,6.,游戏,WC2016绵阳南山,32,好点,坏点,例,6.,游戏,WC2016绵阳南山,33,L,x,y,四,.,斜率优化,WC2016绵阳南山,34,例,7.NOI2007,货币兑换,WC2016绵阳南山,35,例,7.NOI2007,货币兑换,WC2016绵阳南山,36,例,7.NOI2007,货币兑换,WC2016绵阳南山,37,例,7.NOI2007,货币兑换,WC2016绵阳南山,38,例,7.NOI2007,货币兑换,WC2016绵阳南山,39,例,7.NOI2007,货币兑换,WC2016绵阳南山,40,例,7.NOI2007,货币兑换,WC2016绵阳南山,41,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),例,7.NOI2007,货币兑换,WC2016绵阳南山,42,例,7.NOI2007,货币兑换,WC2016绵阳南山,43,例,7.NOI2007,货币兑换,WC2016绵阳南山,44,最优决策,例,7.NOI2007,货币兑换,WC2016绵阳南山,45,j,k,j,k,j,k,例,7.NOI2007,货币兑换,WC2016绵阳南山,46,j,k,l,例,7.NOI2007,货币兑换,WC2016绵阳南山,47,五,.,斜率优化,WC2016绵阳南山,48,六、总结,49,WC2016绵阳南山,