hdu 1085 Holding Bin-Laden Captive! (親関数)
1094 ワード
テンプレートと少し変わっていますが、こちらのコインは数があるので変えます
#include"stdio.h"
int main()
{
int c1[8005],c2[8005],num[3],coin[3]={1,2,5};
int i,j,k,sum;
while(scanf("%d%d%d",&num[0],&num[1],&num[2])!=EOF)
{
if(!num[0]&&!num[1]&&!num[2])break;
if(num[0]==0)
{
printf("1
");continue;
}
sum=num[0]+2*num[1]+5*num[2];
for(i=0;i<=8000;i++)
c1[i]=c2[i]=0;
for(i=0;i<=num[0];i++)
c1[i]=1;
for(i=1;i<=2;i++)
{
for(j=0;j<=sum;j++)
{// k , (for(k=0;k+j<=sum;k+=coin[i]))
for(k=0;k*coin[i]+j<=sum&&k<=num[i];k++)
c2[j+k*coin[i]]+=c1[j];
}
for(j=0;j<=sum;j++)
{
c1[j]=c2[j];c2[j]=0;
}
}
for(i=1;i<=8000;i++)
{
if(c1[i]==0)break;
}
printf("%d
",i);
}
return 0;
}