• <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 - 43,  comments - 9,  trackbacks - 0

            http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1586
            題意:
            一共有K(K<=50)種字母,組成一個長度為L(L<=10^18)的串.
            這個串需滿足要求:
            對任意的 1<=i<=L , 以及任意的 1<=k1,k2<=K 且 k1!=k2, 在前綴 s[1..i]中,字母k1的個數和字母k2的個數之差的絕對值<=2.
            例如: abac是合法的; 而abbbc不合法, 因為前綴abbb中字母b和c的個數相差為3.
            建立狀態:
            從<=2 入手找狀態. 可以設前c個字母中, 最小個數為m, 字母數為m的種類為i, m+1的種類為j, m+2的種類為k. 化簡狀態可得 比最小個數多1的種類為i,比最小個數多2的種類為j. 而經過數學推導(不懂), 可知 j+2k<K, 也就是當 c%K 已知時, 可直接由k確定i和j. 這樣狀態數為 50*50=2500, 還是不能用矩陣法. 進一步思考, 由c%K=0時的結果可以推出c%K=1時的結果,遞推可把c%K=0...K-1的結果都求出. 而要求L步的結果數,實際上并不用去管是1步1步走,還是2步2步走. 所以我們可以直接一次走K步! 這樣就把c%K這一維狀態也消除了.
            于是可以設矩陣m[i,j]為c%K=0時,k經過K步從i轉移到j的方法數.
            這樣先求出 L-L%K 步的方法數, 最后 L%K 步直接dp即可.
            整體復雜度為 K^3*log(L/K).

            本題關鍵: 由k和c%K唯一確定i和j; 一次走K步, 消除狀態c%K, 實際上不同c%K對應的狀態是冗余的, 因為不用去管中間的過程.

            posted on 2009-06-29 22:18 wolf5x 閱讀(451) 評論(0)  編輯 收藏 引用 所屬分類: acm_icpc
            <2009年6月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            "Do not spend all your time on training or studying - this way you will probably become very exhausted and unwilling to compete more. Whatever you do - have fun. Once you find programming is no fun anymore – drop it. Play soccer, find a girlfriend, study something not related to programming, just live a life - programming contests are only programming contests, and nothing more. Don't let them become your life - for your life is much more interesting and colorful." -- Petr

            留言簿(3)

            隨筆分類(59)

            隨筆檔案(43)

            cows

            搜索

            •  

            最新評論

            評論排行榜

            一本久久a久久精品亚洲| 久久亚洲精品中文字幕三区| 亚洲Av无码国产情品久久| 久久久久久久免费视频| 漂亮人妻被中出中文字幕久久 | 人妻无码精品久久亚瑟影视| 囯产极品美女高潮无套久久久| 精品熟女少妇av免费久久| 99久久精品免费| 国内精品久久人妻互换| 午夜精品久久久久久久无码| 国产91久久精品一区二区| 久久毛片一区二区| 国产成人久久777777| 久久久亚洲欧洲日产国码aⅴ| 国产午夜精品理论片久久| 性欧美大战久久久久久久久| 精品综合久久久久久88小说| 久久精品人人做人人妻人人玩| 日本久久中文字幕| 日本精品久久久久中文字幕| 亚洲精品乱码久久久久久| 欧美与黑人午夜性猛交久久久| 精品久久久久久亚洲| 色欲久久久天天天综合网精品| 狠狠色丁香久久婷婷综合蜜芽五月| 青青草国产精品久久久久| 久久久久亚洲AV无码麻豆| 99久久99久久精品国产片果冻| 无码任你躁久久久久久| 日韩久久无码免费毛片软件| 国产精品亚洲综合专区片高清久久久 | 久久久久久伊人高潮影院| 麻豆久久| 伊人久久大香线蕉综合热线| 欧美伊人久久大香线蕉综合69| 久久综合九色综合久99| 欧美日韩精品久久久久| 亚洲国产日韩欧美综合久久| 人人狠狠综合久久亚洲| 欧美成人免费观看久久|