• <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 閱讀(274) 評論(0)  編輯 收藏 引用 所屬分類: ACM-DP

            A级毛片无码久久精品免费| 国产精品久久久久久一区二区三区 | 一本一本久久a久久精品综合麻豆| 久久精品综合网| 亚洲国产成人久久精品动漫| 噜噜噜色噜噜噜久久| 久久久国产乱子伦精品作者| 漂亮人妻被中出中文字幕久久 | 一日本道伊人久久综合影| 亚洲精品国产美女久久久| 久久亚洲av无码精品浪潮| 青青青伊人色综合久久| 久久精品一本到99热免费| 久久www免费人成看国产片| 天天综合久久久网| 精品久久久久久国产| 久久人人爽人人爽人人片av麻烦| 精品蜜臀久久久久99网站| 久久99精品国产99久久6男男| 国内精品久久久久久99蜜桃| 香蕉久久久久久狠狠色| 国産精品久久久久久久| 久久99精品国产麻豆宅宅| 亚洲AV无码一区东京热久久| 四虎影视久久久免费| 久久综合亚洲鲁鲁五月天| 久久精品国产精品亚洲| 思思久久精品在热线热| 欧美亚洲日本久久精品| 99久久人人爽亚洲精品美女| 伊人色综合久久天天| 国产成人精品白浆久久69| 久久久亚洲欧洲日产国码aⅴ| 国产69精品久久久久久人妻精品| 久久99久久99精品免视看动漫| 日韩久久久久中文字幕人妻| 久久久久亚洲精品天堂久久久久久 | 热久久这里只有精品| 久久99国产精品久久99果冻传媒| 精品国产一区二区三区久久久狼| 久久婷婷激情综合色综合俺也去|