# USACO 2.3 Money Systems 货币系统 解题报告

Money Systems

The cows have not only created their own government but they have chosen to create their own money system. In their own rebellious way, they are curious about values of coinage. Traditionally, coins come in values like 1, 5, 10, 20 or 25, 50, and 100 units, sometimes with a 2 unit coin thrown in for good measure.

The cows want to know how many different ways it is possible to dispense a certain amount of money using various coin systems. For instance, using a system of {1, 2, 5, 10, …} it is possible to create 18 units several different ways, including: 18×1, 9×2, 8×2+2×1, 3×5+2+1, and many others.

Write a program to compute how many ways to construct a given amount of money using supplied coinage. It is guaranteed that the total will fit into both a signed long long (C/C++) and Int64 (Free Pascal).

PROGRAM NAME: money
INPUT FORMAT
The number of coins in the system is V (1 <= V <= 25).

The amount money to construct is N (1 <= N <= 10,000). Line 1:  Two integers, V and N
Lines 2..:  V integers that represent the available coins (no particular number of integers per line)

SAMPLE INPUT (file money.in)
3 10
1 2 5

OUTPUT FORMAT
A single line containing the total number of ways to construct N money units using V coins.
SAMPLE OUTPUT (file money.out)
10

PROGRAM NAME: money

INPUT FORMAT:

(file money.in)

OUTPUT FORMAT:

(file money.out)

SAMPLE INPUT
3 10
1 2 5
SAMPLE OUTPUT
10

======================= 华丽的分割线 =======================

看到这题就知道又是最复杂, 最有用的DP问题..(天啊!DP我怎么还没开窍?)
dp方程:
f[j] 代表构造价值为j的方法有多少种?
f[j] += f[j – c[i]]
DP我真的不会解释,, 下次把背包九讲仔细看下!!!
先把代码上上吧~

/*
LANG: C
ID: zqy11001
PROG: money
*/
#include <stdio.h>
#define getint(i) scanf(%d, &i)

long long f[10001];

int main(void)
{
int n, m;
int i, j, k, t;
freopen(money.in, r, stdin);
freopen(money.out, w, stdout);
getint(n);
getint(m);
f[0] = 1;
for(i = 1; i <= n; i++){
getint(t);
for(j = t; j <= m; j++){
f[j] += f[j - t];
}
}
printf(%lld\\n, f[m]);
return 0;
}`