问题1644--【USACO】Dairy Queen(奶品皇后)

1644: 【USACO】Dairy Queen(奶品皇后)

时间限制: 1.000 Sec  内存限制: 64 MB
提交: 25  解决: 19
[提交] [状态] [讨论版] [命题人:]

题目描述

Bessie, always in need of an income, has decided to leverage her dairy skills by taking a part-time job at the local Dairy Queen restaurant. She is running a special cash register (since she has hooves instead of fingers and thus requires special accommodation). Her job is making change for customers as they make a purchase. As she was counting out 83 cents in change, she wondered: "How many ways can I count out 83 cents? I can use three quarters and eight pennies, seven dimes and three pennies, 83 pennies... there must be a zillion ways!" How many different ways can one make change for N (1 <= N <= 300) cents using coins from a set of C (1 <= C <= 8) coins of supplied values C_i (1 <= C_i <= 200)? "Different" means differing counts of coins. Thus, 8 cents can be made, in American currency, with 1 five-cent piece + 3 one-cent pieces and also with 8 one-cent pieces. Using 3 one-cent pieces + 1 five-cent piece is the same as 1 five-cent piece + 3 one-cent pieces, so one can create eight cents in just two different ways. Note that some coin systems are poor at making change and result in an answer of '0'. Coin values in the input file are listed in descending order from largest to smallest. All coin values will be distinct. HINT: Consider recursion as a solution technique.


奶牛Bassie去DQ打工,遇到一个客人给了一张好大面值的钞票,于是Bassie不得不为了给这位顾客找零而面对这样一个问题:现在店里一共有n种硬币,对这些不同种的硬币进行编号,编号为i的硬币面值为a[i] 。因为奶牛的手指头是有限的,因此他只能向你求助啦。(已知总需找零数为total)(1<=total<=1000,1<=n<=1000,1<=a[i]<=300)

求一共有多少种解决方案?


输入

* Line 1: Two space-separated integers: N and C 
* Lines 2..C+1: Line i+1 contains a single integer: C_i

第一行为硬币总值total和硬币种类数n。

以下n行为数值a[i],i=1,2,3...n


输出

* Line 1: A single line with a single integer that is the number of ways to create N cents of change using the supplied coins. The answer is guaranteed to fit into a signed 32-bit integer.

一行,解决方案数


样例输入 复制

83 5 50 25 10 5 1

样例输出 复制

159

提示

INPUT DETAILS: 
Eight-three cents; standard American coins with values 50, 25, 10, 5, and 1 
OUTPUT DETAILS: 
Here are 15 of the 159 ways of making 83 cents: 0 x 50 0 x 25 0 x 10 0 x 5 83 x 1 0 x 50 0 x 25 0 x 10 1 x 5 78 x 1 0 x 50 0 x 25 0 x 10 2 x 5 73 x 1 0 x 50 0 x 25 0 x 10 3 x 5 68 x 1 0 x 50 0 x 25 0 x 10 4 x 5 63 x 1 0 x 50 0 x 25 0 x 10 5 x 5 58 x 1 0 x 50 0 x 25 0 x 10 6 x 5 53 x 1 0 x 50 0 x 25 0 x 10 7 x 5 48 x 1 0 x 50 0 x 25 0 x 10 8 x 5 43 x 1 0 x 50 0 x 25 0 x 10 9 x 5 38 x 1 0 x 50 0 x 25 0 x 10 10 x 5 33 x 1 0 x 50 0 x 25 0 x 10 11 x 5 28 x 1 0 x 50 0 x 25 0 x 10 12 x 5 23 x 1 0 x 50 0 x 25 0 x 10 13 x 5 18 x 1 0 x 50 0 x 25 0 x 10 14 x 5 13 x 1

来源/分类


[提交] [状态]