注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

 
 
 

日志

 
 

HNOI 2008 Day1 玩具装箱 ( BZOJ 1010 ) 1D1D单调性动态规划  

2014-02-23 15:52:03|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
-------------------------------------------------------------------------------------------
最先弄懂的比较直接的方法——队列(并不满足严格的单调性 只不过能凭借决策的单调性删除队首)
显然如果某个状态在当前已无法更新新状态的最小值 则它之后也同样无法更新新状态的最小值
(原因见下文绿字)
先在队列中添加一个起点状态(装好前0个 代价为0)
然后下面的操作重复n次
1.从队首直到队尾循环一遍 如果能够更新当前状态的最小值 则移动队首到当前用来更新的状态
2..把更新完毕的新状态加入队尾
这样的复杂度大概是O(n*min(L/c,n))显然当L/c过大时 是会被卡住的(不过此题还能过)
-------------------------------------------------------------------------------------------
我为何会这么弱 翻遍了好多题解还没看懂二分决策的方法
完全做好这题前先贴个我认为最好理解的题解吧
-------------------------------------------------------------------------------------------
摘自《用单调性优化动态规划》——JSOI2009集训队论文
(部分显示问题不知怎么解决QAQ)
玩具装箱Toy3

?问题描述

n个玩具,要将它们分为若干组进行打包,每个玩具有一个长度len[x]。每一组必须是连续的一组玩具。如果将第x到第y个玩具打包到一组,那么它们的长度,将这组玩具打包所需的代价等于。问将所有玩具打包的最小代价是多少。注意到每组玩具个数并没有限制。n<=5*104

?朴素的解法

仍然可以很轻易的写出一个动态规划的方法:

f(x)代表将前x个玩具打包所需要的最小代价。

,其中代表将的玩具打包所需的费用。

时间复杂度

?正确的解法

     我们如果将每个状态的决策k[x]打印出来列成一张表,会发现这张表是单调非减的,这就说明,决策是单调的。

——有时候考场上紧张没时间证明的话这样做是很好的

      我们不妨暂且不管这是为什么,我们想通过这一单调性来在对数级或者线性时间内解决本题。

      由于决策是单调的,我们可以通过二分查找决策的转折点来在O(nlogn)的时间内解决本题:

      一开始动态规划的边界是f[0]=0。那么,一开始所有状态的最优决策都是0(因为还没有其他状态被计算)。然后,从状态1开始逐步往后扫描,扫描到当前状态i,要保证f[i]已经决策完毕,可以计算出来。

     现在,由于f[i]已经被算了出来,我们尝试寻找哪些后面的状态的决策有可能i。注意到决策是单调的,就是说如果一个状态f[x],他在1i这么多决策中的最优决策是i,那么对于f[y]1i之间的最优决策肯定是i

     这样,我们可以通过二分查找,确定决策i在整个区间中的决策转折点,设转折点为x,那么将[x,n]这个区间,全部上决策i,如果直接O(n)刷色,肯定是不行的,可以通过线段树来完成。这样的时间复杂度是O(nlog2n)的,因为二分查找转折点的时候还要在线段树中用logn的时间计算当前的状态值。

     其实最简单、常数小的算法是用一个栈来实现。

  评论这张
 
阅读(99)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017