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

DYDXH

by dydxh

 
 
 

日志

 
 

DP的重标号技术  

2016-03-13 21:35:02|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
很久之前写题的时候想写一道题...发现不会...查题解说要重标号...没看懂..于是放在了那里...今天mzx告诉我让我看看昨天BC的D...下午看了看...wocao..又是重标号...话说学会了好像也没这么难...
看题解的时候脑袋抽抽了..所以理解了好久....
重标号技术可以解决dp中的后效性并解决无法设立状态的问题...其实很简单..但是很巧妙..

那就用约瑟夫问题说吧,假设有n个人,每次喊k的人被干掉,求最后一个人;
最垃圾的方法就是模拟...然而效率低...
实际上可以用重标号方法实现这个dp,把n个人编号为[0,n-1],然后用F[n]表示剩余n个人的时候谁会活下来;
那么F[n]与F[n-1]有什么关系呢?
可以发现若n>=k第一个死去的人的编号肯定是k-1,而此时只剩下了n-1个人在场上,因为我们已经求出了剩n-1人时从编号为0的人开始报数的幸存者,于是我们是否可以转化一下,使得剩n个人的答案可以从剩n-1个人的答案推出来呢?
很显然是可以的。
假设编号k-1死去了,那么如果此时把原先编号k重标为编号0,那么就又出现了一个从起点开始的约瑟夫问题,而这个问题的答案已经求出来了,于是与重标号前相比,我们仅仅是把每个点的标号减少了k,或者说是增加了n-k,所以在递推的时候在原有的n-1个人基础上加上k即可,于是n个人的约瑟夫问题和n-1个人的约瑟夫问题就可以通过重标号技术来实现转化,从而O(n)时间内可以求出1-n个人的约瑟夫问题的答案;
递推方式:F[1]=0(此处幸存者用的是编号,方便取余)
F[n]=(F[n-1]+k)%n
于是n个人的答案就是F[n]+1;
其实核心就是在一个人阵亡以后对此人的下一人重标号,于是就转化为了更小的子问题;
  评论这张
 
阅读(22)| 评论(1)

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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