hdu1085(母函数解有限个硬币组合问题)

题目链接：hdu1085

/*hdu 1085 Holding Bin-Laden Captive!
大意：
    分别给出1,2,5元硬币的个数，求用这三种硬币不能组合成的最小数值

思路：母函数
    三种硬币组合的情况，可以用下面三个函数的乘积表示：
(1 + x + x^2 + x^3 + ... + x^f[1])(1 + x^2 + x^4 + ... + x^(f[2]*2))(1 + x^5 + x^10 + ... + x^(f[3]*5))
f[1]表示1元硬币的个数，f[2]表示2元硬币的个数，f[3]表示5元硬币的个数
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 8005;
int c1[N], c2[N];
int main()
{
    int i,j;
    int f[5];
    while(scanf("%d%d%d",&f[1],&f[2],&f[3]),(f[1]+f[2]+f[3]))
    {
        int lim = f[1] + f[2]*2 + f[3]*5;//硬币能组成的最大数值
        memset(c1, 0, sizeof(c1));
        memset(c2, 0, sizeof(c2));
        for(i = 0; i <= f[1]; i ++)//初始化
            c1[i] = 1;

        for(i = 0; i <= f[1]; i ++)//第一个括号和第二个括号相乘
            for(j = 0; j <= f[2]*2; j += 2)
                c2[i+j] += c1[i];
        for(i = 0; i <= f[1] + f[2]*2; i ++)
            c1[i] = c2[i], c2[i] = 0;

        for(i = 0; i <= f[1] + f[2]*2; i ++)//前两个括号相乘的结果再乘第三个括号
            for(j = 0; j <= f[3]*5; j += 5)
                c2[i+j] = c1[i];

        for(i = 0; i <= lim; i ++)
        {
            c1[i] = c2[i];
            if(c1[i] == 0)
            {
                printf("%d\n",i);
                break;
            }
        }
        if(i == lim + 1)//大于最大数值
            printf("%d\n",i);
    }
    return 0;
}

hdu1085(母函数解有限个硬币组合问题)

原文：http://blog.csdn.net/jzmzy/article/details/19541685