2014. Dairy QueenConstraints
Time Limit: 1 secs, Memory Limit: 256 MB
Description
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.
Input
Line 1: Two space-separated integers: N and CLines 2..C+1: Line i+1 contains a single integer: C_i
Output
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 int
Sample Input83 550251051Sample Output159Problem Source
每周一赛：2010中山大学新手赛
动态规划：
用ans[i]表示i元钱的组合方法，N表示组成钱目标，c表示每个组成部分
刚开始的时候，由于没有组成部分，所有的组成方案数都为0；
举个例子:
比如读入50块，那么首先ans[50] += 1,这是因为，由于有了整张的50块钱，，ans[50]多了一种组合方式，就是用一张完整的50组成（而不是拆开，比如20+30），然后：
从ans[51]到ans[N]，每个组成钱数的方案都有了新的方案，那就是用一张50加上剩余元钱的组合方法，也即：ans[51] += ans[51 – 50];一张50加上ans[1]的组合方法，下同
ans[52] += ans[52 – 50];
。
。
。
那么两张或者多张50的情况什么时候出现呢？
在这个时候出现：
ans[100] += ans[100 – 50];这个时候，100元的新的组合方式是用一张50在加上另一张50元的组合种数，不就有两张50了么，将新的组合种数加上ans[100]原有的方案数，就是现有的100元的组合方案数；
就这样一直加到ans[N] += ans[N – 50]
OK，代码贴上：
#include <stdio.h>#include <algorithm>#include <string.h>using namespace std;int main() {int ans[305], n, i, c, N;scanf("%d%d", &N, &n);memset(ans, 0, sizeof(ans));while (n–) {scanf("%d", &c);ans[c] += 1;for (i = c + 1; i <= N; i++) {ans[i] += ans[i – c];}}printf("%d\n", ans[N]);return 0;}
寂寞的人总是记住生命中出现的每一个人，
