首页 > 代码库 > UVa 11137 (完全背包方案数) Ingenuous Cubrency
UVa 11137 (完全背包方案数) Ingenuous Cubrency
题意：用13、23……k3这些数加起来组成n，输出总方案数
d(i, j)表示前i个数构成j的方案数则有
d(i, j) = d(i-1, j) + d(i, j - i3)
可以像01背包那样用滚动数组来实现
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 10; 8 long long dp[maxn + 10]; 9 10 int main(void)11 {12 #ifdef LOCAL13 freopen("11137in.txt", "r", stdin);14 #endif15 16 dp[0] = 1;17 for(int i = 1; i <= 21; ++i)18 {19 int v = i * i * i;20 for(int j = v; j <= maxn; ++j)21 dp[j] += dp[j - v];22 }23 int n;24 while(scanf("%d", &n) == 1)25 printf("%lld\n", dp[n]);26 return 0;27 }
UVa 11137 (完全背包方案数) Ingenuous Cubrency
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。