• <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.pku.edu.cn/JudgeOnline/problem?id=1276
            題目大意是:
            給定N種面值分別為d[k]的鈔票,數(shù)量分別為n[k]張.再給一個(gè)整數(shù)cash.
            求,用這些鈔票能表示出的不大于cash的最大值是多少.
            數(shù)據(jù)范圍N<=1000, n[k]<=1000, cash<=100000

            最簡(jiǎn)單的DP思路是大背包.把每一張鈔票看成一件物品,把cash看成背包容量.
            這樣的復(fù)雜度是O(sigma(n[k])*cash),上限是10^11,顯然難以應(yīng)付1000ms的時(shí)限.

            此處便需利用一個(gè)整數(shù)的性質(zhì)來壓縮鈔票數(shù):
            易知,1,2,4,...,2^(k-1)這些數(shù)的線性組合,可以表示出任意小于2^k的正整數(shù).
            所以如果n[i]=2^k-1,那么實(shí)際上鈔票k,就可以轉(zhuǎn)化為分別用系數(shù)(1,2,4,...,2^k-1)去乘d[k]而得到的鈔票各一張.
            如果n[i]!=2^k-1,只需取系數(shù)1,2,4,..,2^(k-1),n[i]-(2^k-1),其中k是使2^k-1<=n[i]的最大整數(shù).

            代碼如下:
             1 #include <iostream>
             2 #include <algorithm>
             3 using namespace std;
             4 int dp[100010],mark;
             5 int sn,cash;
             6 struct BILL{
             7     int n,d;
             8 }b[1010];
             9 int ans;
            10 
            11 void go_dp(){
            12     int i,k,upb,r,s;
            13     dp[0]=mark;
            14     ans=0;
            15     for(k=0; k<sn; k++){
            16         r=1//系數(shù):2的冪次
            17         while(b[k].n>0){
            18             if((r<<1)-1>b[k].n){
            19                 r=b[k].n-(r-1);
            20                 b[k].n=0;
            21             }
            22             s=r*b[k].d; //新鈔票的面值
            23             upb=min(ans+s,cash);
            24             for(i=upb; i>=s; i--){
            25                 if(dp[i-s]==mark){
            26                     dp[i]=mark;
            27                     if(ans<i) ans=i;
            28                 }
            29             }
            30             r<<=1;
            31             if(ans==cash) return;
            32         }
            33     }
            34 }
            35 
            36 int main(){
            37     int i,j,k;
            38     mark=0;
            39     while(scanf("%d%d",&cash,&sn)!=EOF){
            40         ans=0; mark++;
            41         for(i=0;i<sn;i++){
            42             scanf("%d%d",&b[i].n,&b[i].d);
            43             ans+=b[i].n*b[i].d;
            44         }
            45         if(ans>cash)
            46             go_dp();
            47         
            48         printf("%d\n",ans);
            49     }
            50     return 0;
            51 }
            52 

            另,在網(wǎng)上搜得另一種思路,開bool數(shù)組記錄每個(gè)總額是否能達(dá)到,開個(gè)2維數(shù)組記錄達(dá)到相應(yīng)總額每種鈔票使用數(shù)
            個(gè)人以為,這種方法不能保證總得到最優(yōu)解.考察如下的例子:
            cash=3*4*5=60
            鈔票(面值*張數(shù)):3*19,4*14,5*11
            假設(shè)55的方案恰好是5*11,56的方案恰好是4*14,57的方案恰好是3*19,那么在考慮60時(shí)就找不到解了.實(shí)際上60是可以達(dá)到的.





            posted on 2009-04-11 13:21 wolf5x 閱讀(419) 評(píng)論(0)  編輯 收藏 引用 所屬分類: acm_icpc
            <2009年9月>
            303112345
            6789101112
            13141516171819
            20212223242526
            27282930123
            45678910

            "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

            搜索

            •  

            最新評(píng)論

            評(píng)論排行榜

            久久综合九色综合网站| 国产精品久久成人影院| 国产精品免费久久| 欧美一区二区精品久久| 一本一道久久精品综合| 久久亚洲AV永久无码精品| 久久受www免费人成_看片中文| 2020最新久久久视精品爱| 久久AAAA片一区二区| 久久久国产视频| 精品国产一区二区三区久久久狼| 99久久久久| 久久久无码精品亚洲日韩蜜臀浪潮| 久久精品国产99久久久| 久久国产高清一区二区三区| 综合人妻久久一区二区精品| 久久综合欧美成人| 久久人人爽人人爽人人片AV不| 久久久久久亚洲AV无码专区| 久久久久亚洲AV成人网| 久久久久久久久无码精品亚洲日韩 | 亚洲国产精品综合久久网络 | 少妇被又大又粗又爽毛片久久黑人| 一本色综合久久| 国产精品99久久久久久董美香 | 久久综合九色综合97_久久久| 久久久久亚洲AV无码专区首JN| 成人精品一区二区久久久| 久久久无码精品亚洲日韩蜜臀浪潮| 久久精品18| 久久99精品久久久久久噜噜| 欧美亚洲国产精品久久蜜芽| 国产精品久久久久久搜索| 一本色道久久88—综合亚洲精品| 久久se这里只有精品| 国产毛片久久久久久国产毛片 | 国产精品99久久久精品无码| 久久久艹| 手机看片久久高清国产日韩| 国产成人精品久久亚洲| 国产激情久久久久影院小草 |