首页 > 代码库 > hdu 1398 Square Coins(母函数|完全背包)
hdu 1398 Square Coins(母函数|完全背包)
http://acm.hdu.edu.cn/showproblem.php?pid=1398
题意:有价值为1^2,2^2....7^2的硬币共17种,每种硬币都有无限个。问用这些硬币能够组成价值为n的钱数共有几种方案数。
母函数:
#include <stdio.h> #include <iostream> #include <map> #include <set> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> #define LL long long #define _LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; int c1[310],c2[310]; int main() { int n; for(int i = 0; i <= 300; i++) { c1[i] = 1; c2[i] = 0; } for(int i = 2; i <= 17; i++) { for(int j = 0; j <= 300; j++) { for(int k = 0; k+j <= 300; k += i*i) //增量变为i*i c2[k+j] += c1[j]; } for(int j = 0; j <= 300; j++) { c1[j] = c2[j]; c2[j] = 0; } } while(~scanf("%d",&n)&&n) { cout << c1[n] << endl; } return 0; }
完全背包:每种物品都有一定的价值i*i,数目有无限件,那么价值为v的背包能放下物品组合的种类为
f[v] = sum{f[v-k*val[i]] | c[i]*k <= V}。初始化f[0] = 1.
#include <stdio.h> #include <iostream> #include <map> #include <set> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> #define LL long long #define _LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; int dp[300]; int main() { int n; while(~scanf("%d",&n)&&n) { memset(dp,0,sizeof(dp)); dp[0] = 1; for(int i = 1; i <= 17; i++) { for(int j = i*i; j <= n; j++) dp[j] += dp[j-i*i]; } printf("%d\n",dp[n]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。