usaco_4_1_1_nuggets-数学问题+背包.cpp

usaco自己做的1到5章的代码

/*
PROB: nuggets
LANG: C++
*/
/*
关于x,y的二元一次方程ax+by=c (a,b,c∈N*)，若gcd(a,b)=c，则原方程必然有整数解(证明请参看扩展欧几里德算法有关内容)

此时ax+by=kc(k∈Z)必然有整数解。当c=1即gcd(a,b)=1时，ax+by在x,y∈Z范围内可以构成全体整数

回到这道题，这里a,b代表两种包装的麦香牛块的块数，x,y对应两种包装使用的数量。但由于x,y∈N，所以当gcd(a,b)=1时，ax+by不一定能构成全体正整数，但一定能构成≥a*b的全体整数

再扩展，现在有a1,a2…an这些包装。如果所有这些数的最大公约数为1，那么必然ai中最大的两个数ap,aq的乘积以后的数都可以构成。

最大不能达到的就在0~ap*aq这个范围里用背包做就行了。

至于另一种情况，a1,a2…an最大公约数不为1时，就不存在最大不能达到的数
*/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<fstream>
#include<memory>
#define MAXN 256*255
#define cin fin
using namespace std;
ifstream fin("nuggets.in");
ofstream fout("nuggets.out");
int gcdf(int a,int b)
{
	if(a<b) swap(a,b);
	while(b!=0)
	{
		int t=b;
		b=a%b;
		a=t;
	}
	return a;
}

int main()
{
	bool maket[MAXN];
	int ti[255];
	int i,j,k,n,m1=0,m2=1;
	memset(maket,false,sizeof(maket));
	cin>>n;
	for(i=0;i<n;i++)
	{
		cin>>ti[i];
		if(ti[i]>m1) {m2=m1;m1=ti[i]; }
		else if(ti[i]>m2) m2=ti[i];
	}
	if(n==1) {fout<<n-1<<endl; exit(0);}
	else	k=gcdf(ti[0],ti[1]);
	for(i=1;i<n;i++)
	{
		k=gcdf(k,ti[i]);
	}
	if(k!=1) {fout<<'0'<<endl;exit(0);}
	maket[0]=true;
	for(i=0;i<=m1*m2;i++){
		if(!maket[i]) continue;
		for(j=0;j<n;j++)
			maket[i+ti[j]]=true;		
	}
	for(i=m1*m2;i>=0;i--) if(!maket[i]) {fout<<i<<endl;break;}
//	system("PAUSE");
	return 0;
}