首页 > 代码库 > HDU 1085 Holding Bin-Laden Captive! 活捉本拉登（AC代码）普通型母函数
HDU 1085 Holding Bin-Laden Captive! 活捉本拉登（AC代码）普通型母函数
题意：有面值分别为1、2、5的硬币，分别有num_1、num_2、num_5个，问不能组成的最小面值是多少？（0<=每种硬币个数<=1000，组成的面值>0)
思路：母函数解决。只有3个括号要作乘法，分别代表面值1、2、5所能组成的情况。需要两个数组，所能组成的最大值为num_1+2*num_2+5*num_5。如果在这个范围内都能组成，那么最小不能组成的面值为num_1+2*num_2+5*num_5+1。若没有1分钱的硬币，那么不能组成的肯定是1了。
数组的用法：ans[]保存第一个括号→sup保存前两个括号的结果→ans[]保存最后结果。
1 #include <iostream> 2 #define N 8100 3 using namespace std; 4 int num_1,num_2,num_5,ans[N],sup[N],tar; 5 int cal_and_search() 6 {//ans[]→sup[]→ans[] 7 int i,j,k; 8 num_2*=2; 9 num_5*=5;10 memset(ans,0,sizeof(ans)); //清零11 memset(sup,0,sizeof(sup));12 for(i=0;i<=num_1;i++) //初始化num_1+1个喔13 ans[i]=1;14 for(j=0;j<=num_2;j+=2)//头两个括号相乘15 for(k=0;k<=num_1;k++)16 sup[j+k]+=ans[k];17 memset(ans,0,sizeof(ans)); //ans置零18 for(j=0;j<=num_5;j+=5) //上一步结果*第3个括号19 for(k=0;k<=num_1+num_2;k++)20 ans[j+k]+=sup[k];21 for(i=1;i<=N;i++) //搜索22 if(ans[i]==0) return i;23 }24 int main()25 {26 while(scanf("%d%d%d",&num_1,&num_2,&num_5))27 {28 if(num_1==0&&num_2==0&&num_5==0) return 0; //结束29 if(num_1==0){printf("1\n");continue;}30 tar=cal_and_search();31 printf("%d\n",tar);32 }33 return 0;34 }
HDU 1085 Holding Bin-Laden Captive! 活捉本拉登（AC代码）普通型母函数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。