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


            无码国内精品久久人妻蜜桃| 欧美久久久久久午夜精品| 久久亚洲私人国产精品| 国产一区二区三区久久精品| 国产精品免费看久久久| 久久免费99精品国产自在现线| 午夜福利91久久福利| 久久狠狠高潮亚洲精品| 久久久精品国产Sm最大网站| 久久精品国产亚洲AV影院| 韩国无遮挡三级久久| 国产精品美女久久福利网站| 成人综合伊人五月婷久久| 久久久久无码中| 国产韩国精品一区二区三区久久 | 久久国产成人| 国内精品久久人妻互换| 伊人久久五月天| 国产免费久久久久久无码| 国产亚洲精久久久久久无码| 久久久久国产一级毛片高清板| 久久精品人成免费| 精品综合久久久久久97| 亚洲国产成人久久综合一区77| 91精品国产高清久久久久久io| 久久久久久久免费视频| 热RE99久久精品国产66热| 99热成人精品免费久久| 97精品国产91久久久久久| 麻豆AV一区二区三区久久| 久久只有这里有精品4| 久久久噜噜噜久久中文字幕色伊伊| 久久精品九九亚洲精品天堂| 久久亚洲美女精品国产精品| 色狠狠久久综合网| 国产精品中文久久久久久久 | 久久久久久久精品妇女99 | 99久久精品国产高清一区二区 | 亚洲精品无码久久千人斩| 亚洲国产另类久久久精品小说 | 性欧美丰满熟妇XXXX性久久久|