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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

noi2010旅行路线  

2010-10-07 13:43:40|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这题可是让我耿耿于怀的一道题。
在看到它的第一眼,我就知道应该用带状态压缩的dp,不过考场上功力不足,没有写出来。
在考场上,我的思路是:设f(i,a,b,c,d)表示第i行的三个数为a,b,c,且他们的“状态”为d的情况下,方法总数。
我开始认为这个“状态”并不是很多,应该只有26种情况,分类讨论一下就行了。
但是开始写代码的时候,我发现,写一个26*26的状态转移方程可不是人能够搞定的。

之后一段时间,我想到:向f添加一个维度:f(i,j,a,b,c,d),表示现在要填第i行第j个格子了,
而“与他有关”的格子里的数分别是a,b,c,他们的“状态”是d的情况下方案总数。
例如:
xxx
x##
#?0
000
这样一个方格,带x的是已经填好的,带0的是没有填的,我们现在要填有?的格子了,
那么与他有关的格子就是带有#的格子。
而状态的定义方法,我是本着这样一个思想:
如果一个方阵里每个数p都挨着p+1和p-1,那么这个方阵一定代表了一条从1走到N*M的路线。
这样,“状态”的定义就是:a,b,c这三个数他们的前驱和后继是否分别已经挨着他们了。
这样,分类讨论的工作急剧减小,代码量只剩下了4K
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/noi2010/trip^_try.cpp
不过,悲情的是,用3*25的全是0的数据测试,TLE+MLE
而用3*20的数据,刚刚不TLE,用3*25的数据,刚刚不MLE

怎么办呢?

baidu一下,发现有个神牛写了一个dp的程序
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/noi2010/trip^_fromweb.cpp
(十分抱歉,忘记原url了,无法注明出处)
经过我的测试,对3*50的极限数据能够在25s内出解(内存使用40M)
仔细研读它的6K的代码,我发现了几个不同之处:
1.用”插头“和括号序列维护连通性(请百度《基于连通性状态压缩的动态规划问题》)
2.加强版滚动数组

我测试了一下,不用”每个数都要和他的前驱与后继相邻“,
而是用括号序列直接维护一条路线的连通性,
能够让状态总数大大减小(为什么呢?)。
当然,这里记录的”插头”还要包含插头的“方向”。

而“加强版滚动数组”的思路如下:
从后向前dp(从f(N-1,M-1,..)开始算起,每算完一个f(i,j,...),就向他的前驱们f(i,j-1,...)累加结果),
然后把dp写成bfs的样式(用一个队列维护当前还没有向前贡献的状态)
这样,从队列头出去的状态所占用的内存就可以被释放了。
经试验,这个优化能够极大地减小内存的使用量。

剩下的就是写吧。
我十分痛苦地写了7KB的代码,十分纠结地调试了半个小时,终于,搞定了!
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/noi2010/trip^_mytry.cpp
有些地方要注意:
1.写个Hash来管理状态
2.动态申请内存的时候,最好”少次多量“,否则new内存的时间可能让程序TLE得很惨。
3.释放内存的时候,就不要delete了,自己用栈写一个内存回收吧。
4.不要吝惜函数调用的时间,能把代码长度缩下来才是王道

我测试了一下,3*50的极限数据只用了18秒,内存使用11M(惊奇吧!)
看来我写的常数并不是很惨。

由于我的机器比较慢,我猜想考试的时候把这个代码交上去就应该过了。不过,我觉得考试的时候
我一定没有能力去写出来,有能力也不一定有勇气。
至于进一步优化,我的想法如下:
1.强剪枝。绝大多数状态都没有最终贡献到答案里,所以剪枝的效果应该很好。
2.分治。这里只分治一次,即把格子分成上下两个部分,最后用乘法原理统计答案。
3.挤常数。不过,这个常数可不好挤。甚至神奇的-O2编译优化只能让程序快20%。

另附暴力搜索代码(对拍用,不过听说能得很多分)
从讲题会上听了一个能骗好多分的暴力搜索算法
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/noi2010/trip^_force.cpp
和一个优化了的暴力(快几十倍)
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/noi2010/trip^_f2.cpp
  评论这张
 
阅读(1971)| 评论(9)
推荐 转载

历史上的今天

评论

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

页脚

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