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

            ArcTan

            dfs
            隨筆 - 16, 文章 - 117, 評論 - 6, 引用 - 0
            數據加載中……

            白書上的動態規劃D---dp組合計數問題

            Coin Change 

            Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make changes with these coins for a given amount of money.


            For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent coin, two 5-cent coins and one 1-cent coin, one 5-cent coin and six 1-cent coins, or eleven 1-cent coins. So there are four ways of making changes for 11 cents with the above coins. Note that we count that there is one way of making change for zero cent.


            Write a program to find the total number of different ways of making changes for any amount of money in cents. Your program should be able to handle up to 7489 cents.

            Input 

            The input file contains any number of lines, each one consisting of a number for the amount of money in cents.

            Output 

            For each input line, output a line containing the number of different ways of making changes with the above 5 types of coins.

            Sample Input 

            11 26 

            Sample Output 

            4 13 

            題目大意:

             給定1 5 10 25 50五種硬幣,給定一個數,問用這些硬幣有多少種不同的組合方式?

            想想好像可以是一個方程組求解的問題嘛:

                            x1+5*x2+10*x3+25*x4+50*x5=x0;

                            給定x0,一組滿足條件的x>=0就是解集。啊哈哈哈。可以高斯消元法咯。

            不過,明顯的計數問題:

            dp[i][j]表示i可以由前j種硬幣表示的方法數。

            dp[i][j]=dp[i][j-1]+dp[i-coin[j]][j]     i-coin[j]>0

            dp[i][j]=dp[i][j-1]+1  i-coin[j]=0;

            dp[i][j]=dp[i][j-1] i-coin[j]<0

            總結:

                  方程類問題,一定要先把方程寫清楚!!!

            #include<stdio.h>
            #include<string.h>
            #include<math.h>
            long long dp
            [7500][5],coin[5]={1,5,10,25,50};
            int GetAns()
            {
                int i
            ,j;
                memset(dp,0,sizeof(dp));
                dp[1][0]=dp[1][1]=dp[1][2]=dp[1][3]=dp[1][4]=1;
                for (i=2;i<=7489 ;i++ )
                {
                    dp
            [i][0]=1;
                    for (j=1;j<5 ;j++ )
                        if (i-coin[j]>0)
                            dp
            [i][j]=dp[i][j-1]+dp[i-coin[j]][j];
                        else
                            if (i-coin
            [j]==0)
                                dp
            [i][j]=dp[i][j-1]+1;
                            else
                                dp
            [i][j]=dp[i][j-1];
                }
            }
            int main()
            {
                int n
            ;
                GetAns();
                while (scanf("%d",&n)==1)
                    printf(
            "%lld\n",dp[n][4]);
                return 0;
            }


            額額,dp是個好東西,該看看優化了!!!

            posted on 2012-04-29 19:11 wangs 閱讀(852) 評論(0)  編輯 收藏 引用 所屬分類: ACM-DP

            久久久亚洲欧洲日产国码二区| 偷窥少妇久久久久久久久| 四虎国产精品免费久久| 国产一区二区精品久久凹凸| 91久久精品电影| 久久中文字幕人妻熟av女| 亚洲色婷婷综合久久| 国产一级做a爰片久久毛片| 人人狠狠综合久久亚洲| 国产精品乱码久久久久久软件 | 一本久久a久久精品综合夜夜| 国产精品久久久久乳精品爆| 久久久久久人妻无码| 久久播电影网| 久久婷婷国产综合精品| 久久久久久久女国产乱让韩| 久久成人精品| av无码久久久久不卡免费网站| 久久婷婷人人澡人人爽人人爱| 狠狠干狠狠久久| 欧美牲交A欧牲交aⅴ久久| 亚洲欧美国产日韩综合久久 | 看久久久久久a级毛片| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 7777久久亚洲中文字幕| 青青草原精品99久久精品66| 午夜精品久久久久久影视777| 久久电影网一区| 无码超乳爆乳中文字幕久久 | 超级碰碰碰碰97久久久久| 亚洲成色999久久网站| 996久久国产精品线观看| A级毛片无码久久精品免费| 2021最新久久久视精品爱| 久久高清一级毛片| 国产精品成人99久久久久91gav | 久久久久亚洲AV无码专区网站| 久久一区二区三区99| 9191精品国产免费久久| 91精品久久久久久无码| 青青国产成人久久91网|