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

            伊人久久大香线蕉亚洲| 久久99精品国产麻豆不卡| 亚洲国产成人精品女人久久久 | 亚洲国产成人久久综合碰碰动漫3d | 久久久久亚洲AV成人网人人网站| 欧美激情一区二区久久久| .精品久久久麻豆国产精品| 精品久久久久久久久久久久久久久 | 精品久久久久中文字幕一区| 麻豆久久| av无码久久久久久不卡网站| 亚洲综合伊人久久大杳蕉| 国内精品久久久久影院优 | 怡红院日本一道日本久久 | 亚洲国产成人久久精品99| 国产精品久久久久9999高清| 精品久久久久久久中文字幕| 7777久久久国产精品消防器材| 亚洲国产精品久久久久婷婷软件| 久久精品国产久精国产一老狼| 久久成人国产精品一区二区| 日本久久久久亚洲中字幕| 久久久久久曰本AV免费免费| 色成年激情久久综合| 青青草原综合久久| 婷婷久久香蕉五月综合加勒比| 狠狠综合久久综合88亚洲| 久久精品无码一区二区日韩AV| 99久久伊人精品综合观看| 国产精品va久久久久久久| 精品久久久久久成人AV| 亚洲国产精品无码久久一区二区| 亚洲?V乱码久久精品蜜桃| 精品久久人人做人人爽综合| 久久精品视频网| 欧美久久久久久精选9999| 亚洲国产二区三区久久| 91久久国产视频| 久久精品无码av| 亚洲天堂久久久| 日韩精品无码久久久久久|