• <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
            數(shù)據(jù)加載中……

            白書上的動態(tài)規(guī)劃D---dp組合計數(shù)問題

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

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

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

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

            不過,明顯的計數(shù)問題:

            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é):

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

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

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

            狠狠人妻久久久久久综合蜜桃| 狠狠色婷婷久久一区二区三区| 久久综合久久综合久久综合| 97r久久精品国产99国产精| 51久久夜色精品国产| 思思久久好好热精品国产| 久久久国产乱子伦精品作者| 人人狠狠综合久久亚洲婷婷| 合区精品久久久中文字幕一区| 亚洲av伊人久久综合密臀性色 | 精品久久久无码21p发布| 2022年国产精品久久久久| 午夜精品久久久久久| 国产精品99久久99久久久| 亚洲精品综合久久| 久久se精品一区精品二区| 日韩电影久久久被窝网| 99久久人妻无码精品系列蜜桃| 久久婷婷五月综合成人D啪| 国产精品福利一区二区久久| 伊人色综合久久天天人手人婷 | 亚洲国产精久久久久久久| 狠狠综合久久综合88亚洲| 精品久久人人爽天天玩人人妻| 久久精品水蜜桃av综合天堂 | 国内精品久久久久影院老司 | 精品久久久久久久无码| 久久强奷乱码老熟女网站| 久久亚洲国产精品123区| 人人狠狠综合久久亚洲婷婷| 97久久精品人妻人人搡人人玩 | 亚洲午夜久久久| 国内精品久久久久国产盗摄| 久久精品男人影院| 热久久国产精品| 精品99久久aaa一级毛片| 色综合久久最新中文字幕| 久久青草国产精品一区| 99久久www免费人成精品| 2020最新久久久视精品爱| 国产精品美女久久久久av爽|