HDU1085 Holding Bin-Laden Captive!(母函数)

Holding Bin-Laden Captive!

题意

有面值为1、2、5的三种硬币，给你三个数字分别表示拥有的硬币数量，问最小的不能组成的面值为多少?

1<=n<=1000

思路

just母函数，x上的指数代表v[i]*num，比如面值为2的硬币有3枚，那么就可以组成这样的多项式：

$$
1+x^2+x^4+x^6
$$
然后套模板就行。

看！代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a1,a2,a3;
    int v[3]={1,2,5};
    int n[3]={0,0,0};
    int n2[3];

    while(~scanf("%d%d%d",&n2[0],&n2[1],&n2[2]))
    {
        if(n2[0]==0&&n2[1]==0&&n2[2]==0) break;
        int a[10000]={0},b[10000];
        a[0]=1;

        int last=0;
        int P=n2[0]+n2[1]*2+n2[2]*5;
        int K=3;
        for (int i=0;i<K;i++)
        {
            int last2=min(last+n2[i]*v[i],P);//计算下一次的last
            memset(b,0,sizeof(int)*(last2+1));//只清空b[0..last2]
            for (int j=n[i];j<=n2[i]&&j*v[i]<=last2;j++)//这里是last2
                for (int k=0;k<=last&&k+j*v[i]<=last2;k++)//这里一个是last，一个是last2
                    b[k+j*v[i]]+=a[k];
            memcpy(a,b,sizeof(int)*(last2+1));//b赋值给a，只赋值0..last2
            last=last2;//更新last
        }
        int flag=0;
        for(int i=0;i<=P;i++)
        {
            if(a[i]==0)
            {
                flag=1;
                break;
            }
        }
        if(!flag) printf("%d\n",P+1);
        else printf("%d\n",i);
    }
    return 0;
}