钱币兑换问题（完全背包）

钱币兑换问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 8865    Accepted Submission(s): 5349

Problem Description

在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。

 

Input

每行只有一个正整数N，N小于32768。

 

Output

对应每个输入，输出兑换方法数。

 

Sample Input

2934 12553

 

Sample Output

718831 13137761

 

Author

SmallBeer(CML)

 

Source

杭电ACM集训队训练赛（VII）

 

题解：母函数超时，完全背包；

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN = 32800;
int bag[MAXN];
/*
typedef long long LL;
LL a[MAXN], b[MAXN];
int main(){
    int N;
    while(~scanf("%d", &N)){
        for(int i = 0; i <= N; i++){
            a[i] = 1;b[i] = 0;
        }
        for(int i = 2; i <= 3; i++){
            for(int j = 0; j <= N; j++){
                for(int k = 0; k + j <= N; k += i){
                    b[k + j] += a[j];
                }
            }
            for(int j = 0; j <= N; j++){
                a[j] = b[j]; b[j] = 0;
            }
        }
        printf("%lld
", a[N]);
    }
    return 0;
}
*/
int main(){
    int N;
    while(~scanf("%d", &N)){
        memset(bag, 0, sizeof(bag));
        bag[0] = 1;
        for(int i = 1; i <= 3; i++){
            for(int j = i; j <= N; j++){
                bag[j] += bag[j - i];
            }
        }
        printf("%d
", bag[N]);
    }
    return 0;
}