• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            算法學社
            記錄難忘的征途
            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 西月弦 閱讀(1162) 評論(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... 我也分不清啦~~  回復  更多評論
              
            久久―日本道色综合久久| AV色综合久久天堂AV色综合在| 亚洲精品国产字幕久久不卡| 伊人伊成久久人综合网777| 蜜桃麻豆WWW久久囤产精品| 欧美午夜精品久久久久免费视| 91亚洲国产成人久久精品| 久久久久18| 精品久久久久久久久午夜福利| 久久久精品波多野结衣| 亚洲人成网亚洲欧洲无码久久| 亚洲午夜久久久精品影院| 亚洲国产综合久久天堂| 99久久精品免费看国产一区二区三区 | 久久精品国产亚洲AV麻豆网站| 国产精品成人99久久久久 | 亚洲国产天堂久久综合网站| 久久精品无码一区二区三区免费| 国产精品久久久久久吹潮| 久久婷婷五月综合国产尤物app | 97久久久久人妻精品专区 | 中文字幕日本人妻久久久免费| 国产精品女同一区二区久久| 亚洲欧美久久久久9999| 久久国产一片免费观看| 久久A级毛片免费观看| 7777精品伊人久久久大香线蕉| 久久精品亚洲福利| 久久99热狠狠色精品一区| 久久超乳爆乳中文字幕| 亚洲午夜久久久久久久久电影网| 麻豆精品久久久久久久99蜜桃 | 久久精品国产欧美日韩| 97精品伊人久久久大香线蕉| 亚洲AV无码久久精品狠狠爱浪潮| 成人久久免费网站| 欧美精品一区二区久久| 久久青青国产| 久久无码国产专区精品| 国产精品久久久久久久app| 伊人久久无码精品中文字幕|