uva11137Ingenuous Cubrency(完全双肩包）

uva11137Ingenuous Cubrency(完全背包）

题目：Ingenuous Cubrency

题目大意：给出一类钱，面值有1， 8， 27... (21)^3这21种，然后给出N，问N可以有多少组成方式。

解题思路：dp【i】代表面值为i的最多有多少种组合方式，状态转移方程：dp【i】 += dp【i - value【1...21]].  如果要组成i值的话，那么它一定是由之前的状态（i - value【j】）加上现有的面值组成。所以只要遍历一边面值，将之前的状态找出来，然后累加起来就可以了。这里可以用递推，因为状态的计算顺序是知道的。

代码：

#include <cstdio>
#include <cstring>
#include <cmath>

const int N = 21;
const int maxn = 10000;
typedef long long ll;
int value[N];
ll dp[maxn];

void init () {
		
	for (int i = 0; i < N; i++) 
		value[i] = pow (i + 1, 3);
	
	memset (dp, 0, sizeof (dp));
	dp[0] = 1;
	for (int i = 0; i < N; i++) {

		for (int j = 1; j < maxn; j++) {

			if (j >= value[i])
				dp[j] += dp[j - value[i]];
		}
	}
}

int main () {

	init ();
	int n;
	while (scanf ("%d", &n) != EOF) {

		printf ("%lld\n", dp[n]);
	}
	return 0;
}