算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
题目描述:
   求12×12矩阵上的互不嵌套的k个哈密顿回路的方案数。
http://acm.hdu.edu.cn/showproblem.php?pid=4285

算法分析:
   
   求哈密顿路方案数不用多说了,相信大家都会插头DP。
   之前在clarification里面看到有同学说暴空间,相信他一定没刷过sgu 1519...
   离散化解决空间问题,我用的是map。四进制表示状态。

   求k个哈密顿回路就多加一维状态,表示目前已经有了多少组哈密顿回路。

   至于互不嵌套嘛。。。。 好吧,我承认这不是我自己想出来的。。。。 就是在左右括号相遇的时候判断有多少组括号包含了这组括号。
   如果是奇数的话,就跳过这个状态。

   证明如下:
      在外面的括号想要合并,且不包含到当前括号,必须一次合并偶数个。
      
      如果外面有偶数个括号,其实后面未必合法,但是非法的时候一定是奇数个。因为合法的合并都是一次性合并偶数个。。。。


   说的有点乱。。。。然后是trick
   比如1 2 2 0 **\n**这组应该是1。。。 好犀利。。。。。


tianjin2012-online H

   
posted on 2012-09-10 21:09 西月弦 阅读(1059) 评论(5)  编辑 收藏 引用 所属分类: 解题报告

FeedBack:
# re: hdu 4285 插头DP
2012-09-11 10:30 | wuyiqi
ORZ!!!  回复  更多评论
  
# re: hdu 4285 插头DP
2012-09-12 20:01 | foxandhuzh
(##()##)被嵌套的那一对括号肯定不能合并吧,为什么这么判断嵌套是错的?  回复  更多评论
  
# re: hdu 4285 插头DP
2012-09-13 09:56 | 西月弦
@foxandhuzh
因为如果里面的合并了, 那么外面的别无选择,只能合并了.... 这样就形成嵌套了  回复  更多评论
  
# re: hdu 4285 插头DP
2012-09-13 15:48 | XxX_Stu
是ural1519?  回复  更多评论
  
# re: hdu 4285 插头DP[未登录]
2012-09-15 10:43 | figo
@XxX_Stu
就是那个timus... 我也分不清啦~~  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理