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; }