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

            QuXiao

            每天進(jìn)步一點(diǎn)點(diǎn)!

              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
              50 隨筆 :: 0 文章 :: 27 評論 :: 0 Trackbacks

            有N(1<=N<=50)種不同面值郵票,由這些郵票組成面值1~M,1、2、……、M每種面值均由不超過K(1<=K<=200)數(shù)目的郵票組成,求最大的M為多少?郵票最大面值為10000

            一開始想到DP,數(shù)組canComprise[10000*200][200],canComprise[i][j]表示用j張郵票是否可以組成面值i,但數(shù)組太大,放棄。

            后來改用深搜,優(yōu)化了許久,最后幾組數(shù)組仍然超時(shí),放棄。

            又回頭想DP,如果canComprise[i][j1]和canComprise[i][j2]均為true,j1 < j2,那么canComprise[i][j1]肯定是更優(yōu)的解,因?yàn)閖1可以擴(kuò)展更多i+stamps[x]。所以,只要用一維數(shù)組保存答案就可以了,比如minStamp[i] = j就表示組成i所用到的最少郵票數(shù)為j,遞推式很容易想到:

            minStamp[i] = Min{ minStamp[i-stamp[x]] + 1 } ( i – stamp[x] >= 0 )

             

            同一種情況,表達(dá)解的方式可能有多種,盡量使用最精簡的方式,已達(dá)到降維的效果。

            posted on 2011-02-12 11:59 quxiao 閱讀(177) 評論(0)  編輯 收藏 引用

            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            亚洲狠狠婷婷综合久久久久| 日本人妻丰满熟妇久久久久久| 久久午夜无码鲁丝片| 亚洲人成网亚洲欧洲无码久久| 亚洲狠狠婷婷综合久久蜜芽| 久久人人爽人人爽人人AV东京热| 久久福利青草精品资源站| 日本亚洲色大成网站WWW久久| 久久精品国产精品亚洲毛片| 国产精品久久久久久久| 日韩一区二区三区视频久久| 亚洲va久久久噜噜噜久久| 精品久久久久久无码人妻蜜桃| 国产精品乱码久久久久久软件| 97久久香蕉国产线看观看| 青青草原综合久久大伊人导航| 蜜臀av性久久久久蜜臀aⅴ麻豆| 久久国产成人| 97久久精品人人做人人爽| 亚洲女久久久噜噜噜熟女| 91久久精品国产91性色也| 亚洲国产精品成人久久| 久久一区二区免费播放| 久久九九有精品国产23百花影院| 久久久久久精品免费看SSS| 久久AⅤ人妻少妇嫩草影院| 狠狠色丁香久久综合五月| 亚洲综合伊人久久综合| 亚洲精品无码久久毛片| 久久天天躁狠狠躁夜夜av浪潮| 久久99国产亚洲高清观看首页| 亚洲va中文字幕无码久久不卡| 伊人色综合九久久天天蜜桃 | 亚洲欧美一级久久精品| 国产精品青草久久久久福利99| 国产精品一区二区久久国产| 中文字幕无码免费久久| 婷婷久久香蕉五月综合加勒比| 久久久久亚洲av成人网人人软件| 亚洲国产精品无码久久久久久曰| 久久久91人妻无码精品蜜桃HD|