赤裸的完全背包问题
#include <stdio.h> #include <string.h> #define MAXN 10000 #define N 20 long long f[MAXN+1]; int coins[N+1]; void dp() { int i, j; for(i=1; i<=21; ++i) coins[i-1] = i*i*i; memset(f,0,sizeof(f)); f[0] = 1; for(i=0; i<=N; ++i) for(j=coins[i]; j<MAXN; ++j) f[j] += f[j-coins[i]]; } int main() { int amount; dp(); while(~scanf("%d",&amount)) { printf("%lld\n",f[amount]); } return 0; }