hdu1085（生成函数）

题目

我终于会用对拍器了，我总是不敢去尝试新事物，去年就像学，上网搜过几次资料，感觉烦就放弃了，但事实证明其实非常简单，对于我未来的coding生活来说实在是大有裨益，这次就是有一个简单的初始化问题，但自己找一年都不太可能找出来，感谢网上某一篇手把手的教程，没有它或许我永远都不会踏出这一步，希望未来的自己更加勇敢
给出n1个1，n2个2，n3个5进行随意相加，问最小无法组成的数字

题解

背包可以（可惜我不会），生成函数在我看来属于凭借数学能力作弊的方法，复杂的背包思考都不需要，只需要简单的套公式就行了，属于比背包简单的方法（哈？那你还不快学）
1 + x 1 + x 2 + x 3 + . . . . + x n 1 1+x^{1}+x^{2}+x^{3}+....+x^{n1} 1+x1+x2+x3+....+xn1
1 + x 2 + x 4 + x 6 + . . . + x n 2 1+x^{2}+x^{4}+x^{6}+...+x^{n2} 1+x2+x4+x6+...+xn2
1 + x 5 + x 10 + x 15 + . . . + x n 3 1+x^{5}+x^{10}+x^{15}+...+x^{n3} 1+x5+x10+x15+...+xn3
将三个多项式相乘，然后找第一个系数不为0的项

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool a1[8005],a2[8005],a3[8005];
int b[3]={1,2,5},n1,n2,n3;
int main()
{
	int n;
	while(scanf("%d%d%d",&n1,&n2,&n3)==3&&(n1+n2+n3)!=0)
	{
		int m=n1*1+n2*2+n3*5;
		for(int i=0;i<=m+1;i++)
		{
			a2[i]=1;
			a1[i]=1;
			a3[i]=0;
		}
		for(int i=0;i<=n1;i++)
		{
			for(int j=0;j<=2*n2;j+=2)
			{
				a3[i+j]+=a1[i]*a2[j];
				//cout<<i+j<<' '<<a1[i+j]<<endl;
			}
		}
		for(int i=0;i<=m;i++)
		{
			a1[i]=a3[i];
			a3[i]=0;
		}
		for(int i=0;i<=m;i++)
		{
			for(int j=0;j<=5*n3;j+=5)
			{
				a3[i+j]+=a1[i]*a2[j];
				//cout<<i+j<<' '<<a1[i]*a2[j]<<endl;
			}
		}
		for(int i=1;i<=m+1;i++)
		{
			if(a3[i]==0)
			{
				cout<<i<<endl;
				break;
			}
		}
	}
}