• <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ù)加載中……

            白書上的動(dòng)態(tài)規(guī)劃D---dp組合計(jì)數(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五種硬幣,給定一個(gè)數(shù),問用這些硬幣有多少種不同的組合方式?

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

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

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

            不過,明顯的計(jì)數(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是個(gè)好東西,該看看優(yōu)化了!!!

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

            久久狠狠爱亚洲综合影院| MM131亚洲国产美女久久| 国产午夜精品久久久久九九电影 | 亚洲国产欧洲综合997久久| 久久亚洲AV无码精品色午夜 | 亚洲综合伊人久久大杳蕉| 亚洲AV日韩AV天堂久久| 久久午夜电影网| 久久久久亚洲AV无码观看| 久久这里只有精品首页| 久久综合色老色| 亚洲午夜久久久精品影院| 2021国产精品久久精品| 久久99精品国产| 日日躁夜夜躁狠狠久久AV| 久久不见久久见免费影院www日本| 亚洲午夜精品久久久久久浪潮| 久久精品国产精品国产精品污 | 色婷婷久久综合中文久久一本| 久久精品国产亚洲AV无码麻豆| 色综合合久久天天给综看| 久久这里只有精品久久| 日韩乱码人妻无码中文字幕久久 | 精品久久久久久国产牛牛app| 亚洲va久久久噜噜噜久久男同| 久久久精品日本一区二区三区 | 亚洲国产精品无码久久青草| 久久精品人人做人人爽电影| 久久久亚洲欧洲日产国码二区 | 国产午夜电影久久| 久久久精品免费国产四虎| 久久99国产乱子伦精品免费| 亚洲精品无码久久久久去q| 久久人人爽人人人人片av| 国产精品中文久久久久久久| 久久久久亚洲AV成人网人人软件| 国产精品欧美久久久久无广告| 国产女人aaa级久久久级| 久久无码AV中文出轨人妻| 一本久久综合亚洲鲁鲁五月天| 女同久久|