专栏首页mlHDUOJ----Coin Change

HDUOJ----Coin Change

Coin Change

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10590    Accepted Submission(s): 3535

Problem Description

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, or two 5-cent coins and one 1-cent coin, or 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 100 coins.

Input

The input file contains any number of lines, each one consisting of a number ( ≤250 ) 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

Author

Lily

Source

浙江工业大学网络选拔赛

思路: 此题可以采取dfs,但是用分治法还是可以的,优化一下可以达到15ms......

在此贴出代码:

 1 #include<iostream>
 2 using namespace std;
 3 int main()
 4 {
 5     int n,count;
 6     int j,k,m,g,l;
 7     while(cin>>n)
 8     {
 9         count=0;
10         for( j=0;j<=n/50;j++)   //50
11         {  
12             k=m=g=l=0;
13             if(n==j*50+k*25+m*10+g*5+l)
14                         {
15                            count++;
16                            break;
17                         }
18                         else
19                             if(n<j*50+k*25+m*10+g*5+l)
20                                 break;
21 
22             for( k=0;k<=n/25;k++)   //25
23             {
24                 m=g=l=0;
25                 if(n==j*50+k*25+m*10+g*5+l)
26                         {
27                            count++;
28                            break;
29                         }
30                         else
31                             if(n<j*50+k*25+m*10+g*5+l)
32                                 break;
33                 for( m=0;m<=n/10;m++)   //10
34                 {
35                     g=l=0;
36                     if(n==j*50+k*25+m*10+g*5+l)
37                         {
38                            count++;
39                            break;
40                         }
41                         else
42                             if(n<j*50+k*25+m*10+g*5+l)
43                                 break;
44                     for( g=0;g<=n/5;g++)  //5
45                     {
46                         l=0;
47                         if(n==j*50+k*25+m*10+g*5+l)
48                         {
49                            count++;
50                            break;
51                         }
52                         else
53                             if(n<j*50+k*25+m*10+g*5+l)
54                                 break;
55                       for( l=0;l<=100-j-k-m-g;l++)  //1
56                       {
57                         if(n==j*50+k*25+m*10+g*5+l)
58                         {
59                            count++;
60                            break;
61                         }
62                         else
63                             if(n<j*50+k*25+m*10+g*5+l)
64                                 break;
65                        }
66                     }
67                 }
68             }
69         }
70     
71     cout<<count<<endl;
72     }
73 return 0;
74 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 卡特兰数扩展

    对于排队买票问题的一些说法.....   假若有M+ N人去买票,n人手持5元,m人手持10元,而售货阿姨没有零钱,问有多少种方法能使大家都买到票。 其中m<=...

    Gxjun
  • mxnet框架样本,使用C++接口

    哇塞,好久么有跟进mxnet啦,python改版了好多好多啊,突然发现C++用起来才是最爽的. 贴一个mxnet中的C++Example中的mlp网络和实现,感...

    Gxjun
  • c语言格式大整理

    1、C语言中,非零值为真,真用1表示;零值为假,假用0表示。 2、转义字符参考: \a 蜂鸣,响铃  \b 回退:向后退一格 ...

    Gxjun
  • MIT科技评论2018最新全球十大突破技术:人工智能、生物基因技术等上榜

    【导读】自2001年以来,《麻省理工科技评论》(MIT)每年都会评选出10项突破性技术。对于“突破”一词到底如何定义?MIT编辑部表示,可能我们的TOP10里面...

    WZEARW
  • 《selenium2 python 自动化测试实战》(10)——下拉框和alert

    用户2149234
  • 一个故事讲完CPU的工作原理

    上二年级的小明正坐在教室里。现在是数学课,下午第一节,窗外的蝉鸣、缓缓旋转的吊扇让同学们昏昏欲睡。此时,刘老师在黑板上写下一个问题:

    良月柒
  • 一个故事讲完CPU的工作原理

    上二年级的小明正坐在教室里。现在是数学课,下午第一节,窗外的蝉鸣、缓缓旋转的吊扇让同学们昏昏欲睡。此时,刘老师在黑板上写下一个问题:

    黄泽杰
  • [Python人工智能] 一、神经网络入门及theano基础代码讲解

    从本篇文章开始,作者正式开始研究Python深度学习、神经网络及人工智能相关知识。第一篇文章主要讲解神经网络基础概念,同时讲解Theano库的安装过程及基础用法...

    统计学家
  • 如何做一件事情,制定可行的目标,与寻找正确的方法,都比做这件事本身更重要

    笔者最近业余在尝试创作网文小说,但进展缓慢。网文小说看起来很简单,写起来却没那么容易。别人的作品读起来总觉得不过尔尔,总觉得还有许多可以改进的地方;真轮到自己动...

    李艺
  • 求s=1+1(1+2)+1(1+2+3)

    求s=1+1/(1+2)+1/(1+2+3)….+1/(1+2+3….+n)的值 #include <stdio.h> float fun(int n) { ...

    py3study

扫码关注云+社区

领取腾讯云代金券