UVA 11137 Ingenuous Cubrency

UVA_11137

    这个题目实际上就是一个多重背包问题，只不过要求记录的是方案的种数。

#include<stdio.h>
#include<string.h>
#define MAXD 10010
int N;
long long int f[MAXD];
void solve()
{
    int i, j, k;
    memset(f, 0, sizeof(f));
    for(i = 0; i <= N; i ++)
        f[i] = 1;
    for(i = 2; i <= 21; i ++)
    {
        k = i * i * i;
        for(j = k; j <= N; j ++)
            f[j] += f[j - k];
    }
    printf("%lld\n", f[N]);
}
int main()
{
    while(scanf("%d", &N) == 1)
    {
        solve();
    }
    return 0;
}