HDU 1085 Holding Bin-Laden Captive!（母函数）

HDU 1085 Holding Bin-Laden Captive!（母函数）

题目地址

题意： 
给你cnt1个一元硬币，cnt2个两元硬币，cnt3个五元硬币，问不能凑出来的第一个面额是多少。

分析： 
母函数，公式为 
(1+x+x^2+x^3+.........x^cnt1)∗(1+x^2+x^4+x^6+.........x^cnt2)∗(1+x^5+x^10+x^15+............x^cnt5)
直接模拟即可。

代码：

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  File:        1085.cpp
*  Create Date: 2014-05-25 11:34:37
*  Descripton:  Generating Function
*/

#include <cstdio>
#include <cstring>

const int N = 1e4;
int val[3] = {1, 2, 5}, cnt[3];
int c1[N], c2[N], mmax;

int main()
{
	while (~scanf("%d%d%d", &cnt[0], &cnt[1], &cnt[2]) && (cnt[0] || cnt[1] || cnt[2])) {
		memset(c1, 0, sizeof(c1));
		memset(c2, 0, sizeof(c2));

		mmax = 0;
		for (int i = 0; i < 3; i++)
			mmax += cnt[i] * val[i];

		for (int i = 0; i <= cnt[0]; i++)	// 处理第一种硬币
			c1[i] = 1;

		for (int i = 1; i < 3; i++) {	// 对于1后面的每种硬币
			for (int j = 0; j <= mmax; j++) {
				if (c1[j] != 0) {	// 对于之前的项(c1)
					for (int k = 0; k <= val[i] * cnt[i]; k += val[i]) {	// 模拟与当前项式相乘
						if (j + k <= mmax)
							c2[j + k] += c1[j];
					}
				}
			}
			// 把当前项保存在c1，清空c2
			memcpy(c1, c2, sizeof(c1));
			memset(c2, 0, sizeof(c2));
		}

		int i;
		for (i = 0; i <= mmax; i++) {
			if (c1[i] == 0)
				break;
		}
		printf("%d\n", i);
	}
	return 0;
}