• <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, 評(píng)論 - 6, 引用 - 0
            數(shù)據(jù)加載中……

            白書(shū)上的動(dòng)態(tài)規(guī)劃D---dp組合計(jì)數(shù)問(wèn)題

            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五種硬幣,給定一個(gè)數(shù),問(wèn)用這些硬幣有多少種不同的組合方式?

            想想好像可以是一個(gè)方程組求解的問(wèn)題嘛:

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

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

            不過(guò),明顯的計(jì)數(shù)問(wèn)題:

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

            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

            總結(jié):

                  方程類問(wèn)題,一定要先把方程寫(xiě)清楚!!!

            #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是個(gè)好東西,該看看優(yōu)化了!!!

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

            久久国产成人午夜aⅴ影院| 三级三级久久三级久久| 18岁日韩内射颜射午夜久久成人| 丰满少妇人妻久久久久久4| 伊人久久大香线焦AV综合影院| 精品久久久久久国产免费了| 久久综合九色综合欧美狠狠| 国产精品久久久久9999高清| 久久国产亚洲高清观看| 国内精品久久久久影院日本| 亚洲精品无码久久久久去q | 国产免费久久精品99re丫y| 久久精品国产国产精品四凭| 久久久久人妻一区精品| 青青草原综合久久| 久久成人国产精品一区二区| 久久亚洲欧洲国产综合| 香蕉久久夜色精品国产2020| 久久精品国产2020| 久久国产精品77777| 999久久久国产精品| 久久久久久久久久久免费精品| 久久婷婷五月综合成人D啪| 久久精品亚洲AV久久久无码| 麻豆AV一区二区三区久久| 久久精品嫩草影院| 久久综合日本熟妇| 亚洲色欲久久久综合网| 国产A级毛片久久久精品毛片| 久久综合九色欧美综合狠狠 | 精品国产青草久久久久福利| 亚洲AV伊人久久青青草原| 亚洲AV无码一区东京热久久| 国产精品成人无码久久久久久| 亚洲精品97久久中文字幕无码| 久久久噜噜噜久久熟女AA片| 国产香蕉97碰碰久久人人| 亚洲午夜久久久影院| 国产精品内射久久久久欢欢| 2020国产成人久久精品| 国产美女久久久|