本文共 835 字,大约阅读时间需要 2 分钟。
这道题还是可以套一下母函数的模板,稍微改一下即可,不过要注意一些地方,在后面会说明。
代码如下:#include#include #include #include typedef long long ll;using namespace std;ll c1[8005],c2[8005];int main(){ int i,j,k; int num[4],v[4]={0,1,2,5},ma; ll ans; while(~scanf("%d%d%d",&num[1],&num[2],&num[3])&&(num[1]||num[2]||num[3])) { ans=1; ma=num[1]+2*num[2]+5*num[3]; //ma记录用这些硬币最多能兑换的面额 for(i=0;i<=ma+1;i++) //一定要ma+1!!!!!!! 初始化一定要ma+1,因为有可能1~ma所有面额都能兑换,这是不能兑换的最小面额就是ma+1了 c1[i]=c2[i]=0; for(i=0;i<=num[1];i++) // c1[i]=1; for(i=2;i<=3;i++) { for(j=0;j<=ma;j++) for(k=0;(k+j<=ma)&&(k<=v[i]*num[i]);k+=v[i]) //k有两个条件,这是因为每种硬币的数量是有限的 c2[j+k]=c2[j+k]+c1[j]; for(j=0;j<=ma;j++) { c1[j]=c2[j]; c2[j]=0; } } for(i=1;i<=ma+1;i++) if(!c1[i]) { ans=i; break; } printf("%lld\n",ans); } return 0;}
转载地址:http://rbdci.baihongyu.com/