• <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>

            風雪夢

            柳絮因風起

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              4 Posts :: 76 Stories :: 3 Comments :: 0 Trackbacks

            常用鏈接

            留言簿

            我參與的團隊

            搜索

            •  

            最新評論

            • 1.?re: LightOJ1080 Binary Simulation
            • 話說加個PushDown操作不就OK了咩?
            • --仗劍奔走天涯
            • 2.?re: 正式開博
            • 加油!
            • --leafcloudsky
            • 3.?re: 啟航杯啊
            • 太屎了!!我竟然就這么的WA了兩次,最終發現,第四題少了兩句初始化,第五題把數組開錯地方了,算法沒問題,結果就這么從四題跌到二題,太傷不起了!!可憐我調spfa調了一晚上!!尼瑪啊!!
            • --淺雨歌

            閱讀排行榜

            評論排行榜

            題目鏈接:http://poj.org/problem?id=3280

            題目大意就是給你一個字符串,和字符串中每一個字母刪除或者添加所需要付出的代價,問把它變成一個回文字串所需要的最少的代價。

            首先明確一個問題,如果我們在字符串中某一個位置刪除一個字符,那么一定能找到一個等價的添加的方法,所以可以把刪除和添加統一到一起,然后這道題的狀態就簡單了。

            dp[i][j]表示的是區間[i, j]內形成回文串所需要的最少的代價,這樣我們就可以由一個單位字符向外擴展,狀態轉移方程就應該是dp[j][i] = min(dp[j + 1][i] + cost[s[j] - 'a'], dp[j][i - 1] + cost[s[i] - 'a']),另外如果區間的首尾字符都是一樣的話,那么首尾字符全都刪去還是一個回文串,這樣一來再把兩個代價做一個比較就可以了吧。

            當然,其實最初的想法是擴展出來四個狀態,就是首刪除,首添加,尾刪除,尾添加,由此擴展開來求一個最小值,不過看了一下解題報告,再加上和學長們YY一會兒,發現了可以統一的問題,就想出來了。

            view code

            posted on 2013-04-09 20:15 淺雨歌 閱讀(179) 評論(0)  編輯 收藏 引用 所屬分類: DP
            热久久视久久精品18| 久久久久人妻一区二区三区 | 一本大道久久东京热无码AV| 久久夜色精品国产亚洲av| 无码任你躁久久久久久| 亚洲综合伊人久久大杳蕉| 国产精品久久久天天影视| 综合久久一区二区三区 | 午夜精品久久久久久久无码| 狠狠色丁香久久婷婷综合| 色综合久久中文综合网| 日本五月天婷久久网站| 久久亚洲高清观看| 性色欲网站人妻丰满中文久久不卡| 久久精品国产99国产精品澳门| 久久亚洲色一区二区三区| 97久久综合精品久久久综合| 亚洲综合久久久| 久久男人中文字幕资源站| 久久精品国产亚洲av日韩| 色悠久久久久久久综合网| 婷婷综合久久中文字幕| 久久久久国产精品熟女影院| 伊人久久无码精品中文字幕| 精品一久久香蕉国产线看播放| 久久婷婷五月综合色奶水99啪| 中文字幕无码久久久| 欧美粉嫩小泬久久久久久久| 91久久精品电影| 精品国产热久久久福利| 青青青国产精品国产精品久久久久 | 国产福利电影一区二区三区久久久久成人精品综合 | 国产精品免费久久久久久久久| 综合久久国产九一剧情麻豆| 久久无码人妻精品一区二区三区| 国内精品久久九九国产精品| 久久婷婷激情综合色综合俺也去| 亚洲综合伊人久久大杳蕉| 亚洲伊人久久精品影院| 一本一本久久aa综合精品| 亚洲国产精品久久久天堂|