首页 > 代码库 > hdu 1085 Holding Bin-Laden Captive!(母函数)
hdu 1085 Holding Bin-Laden Captive!(母函数)
http://acm.hdu.edu.cn/showproblem.php?pid=1085
题意:1元,2元,5元的硬币分别有num[1],num[2],num[3]个。问用这些硬币不能组合成的最小钱数。
继续母函数。
有两个注意的地方:
对c2[]初始化的同时也要对c1[]初始化。
最后枚举到sum+1,因为存在[1,sum]都可以凑成的可能,这时输出sum+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 c1[8010],c2[8010]; int add[4] = {0,1,2,5}; int num[4]; int main() { while(~scanf("%d %d %d",&num[1],&num[2],&num[3])) { if(num[1] == 0 && num[2] == 0 && num[3] == 0) break; int sum = num[1] + num[2]*2 + num[3]*5; //可以到达的最高钱数 memset(c2,0,sizeof(c2)); memset(c1,0,sizeof(c1)); for(int i = 0; i <= num[1]; i++) { c1[i] = 1; } for(int i = 2; i <= 3; i++) { for(int j = 0; j <= sum; j++) { for(int k = 0; k+j <= sum && k <= add[i]*num[i]; k += add[i]) { c2[k+j] += c1[j]; } } for(int j = 0; j <= sum; j++) { c1[j] = c2[j]; c2[j] = 0; } } for(int i = 1; i <= sum+1; i++) //注意枚举到sum+1,因为若[1,sum]都可以凑成的话,应该输出sum+1. { if(c1[i] == 0) { printf("%d\n",i); break; } } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。