首页 > 代码库 > HDU 1085 Holding Bin-Laden Captive! 母函数
HDU 1085 Holding Bin-Laden Captive! 母函数
这次变成了每一种硬币有数量限制的情况了,用母函数显然可以十分方便的解决
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;typedef long long LL;const int maxn = 1000 + 2 * 1000 + 5 * 1000 + 5;int c1[maxn],c2[maxn],lim[3],val[3] = {1,2,5};int main() { while(scanf("%d%d%d",&lim[0],&lim[1],&lim[2]),lim[0] + lim[1] + lim[2]) { int maxval = lim[0] + 2 * lim[1] + 5 * lim[2]; memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2)); for(int i = 0;i <= lim[0];i++) { c1[i] = 1; } for(int i = 1;i < 3;i++) { for(int j = 0;j <= lim[i];j++) { for(int k = 0;k + j * val[i] <= maxval;k++) { c2[k + j * val[i]] += c1[k]; } } for(int i = 0;i <= maxval;i++) { c1[i] = c2[i]; c2[i] = 0; } } int ans = 0; for(int i = 0;i <= maxval + 10;i++) if(!c1[i]) { ans = i; break; } printf("%d\n",ans); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。