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

            久久99精品国产麻豆宅宅| 伊人久久亚洲综合影院| 2020久久精品亚洲热综合一本 | 久久er国产精品免费观看2| 久久99热精品| 久久天天躁夜夜躁狠狠躁2022| 久久精品a亚洲国产v高清不卡| 久久se这里只有精品| 日日噜噜夜夜狠狠久久丁香五月| 99久久99久久精品国产片| 欧美精品九九99久久在观看| 久久综合综合久久97色| 伊人久久大香线蕉av不变影院| 狠狠精品久久久无码中文字幕| 中文字幕精品无码久久久久久3D日动漫| 狠狠色婷婷久久一区二区| 91精品婷婷国产综合久久| 伊人久久一区二区三区无码| 国产精品青草久久久久婷婷| 亚洲日本va中文字幕久久| 久久青青草原国产精品免费| 精品久久久无码21p发布| 九九热久久免费视频| 青草国产精品久久久久久| 久久久久亚洲爆乳少妇无| 日本一区精品久久久久影院| 久久精品国产亚洲AV蜜臀色欲 | 热久久国产精品| 久久精品国产亚洲av日韩| 久久婷婷人人澡人人爽人人爱 | 国产精品美女久久久久av爽| 久久精品成人国产午夜| 亚洲AV无码一区东京热久久| 久久亚洲美女精品国产精品| 久久久久久久久66精品片| 久久99精品九九九久久婷婷| 天天综合久久久网| 久久精品国产99国产电影网| a级成人毛片久久| 久久精品www| 国产精品综合久久第一页|