Home > Old Blog Posts > USACO 4.1.1 Beef McNuggets

USACO 4.1.1 Beef McNuggets


nocow上给了一个并没有被严格证明的结论:结果不会超过最大的两个数的最小公倍数

于是数论知识贫乏的我就猥了

除了这步,算法就是一个裸的背包,此处从略

/*
ID: dementr1
PROG: nuggets
LANG: C++
*/
#include
#include
using namespace std;
ifstream fin("nuggets.in");
ofstream fout("nuggets.out");
int a[20],N,mini=-1;
bool f[70000]={false};
void init()
{
	int i;
	fin>>N;
	for(i=0;i>a[i];
		if(mini==-1||a[i]<mini) mini=a[i];
	}
}
void work()
{
	int i,j,ans;
	for(i=2;i<=mini;i++)
	{
		bool flag=true;
		for(j=0;j<N;j++)
			if(a[j]%i!=0)
			{
				flag=false;
				break;
			}
		if(flag)
		{
			fout<<0<<endl;
			return;
		}
	}
	f[0]=true;
	for(i=0;i<=65792;i++)
		for(j=0;j<N;j++)
		{
			if(f[i])
				f[i+a[j]]=true;
			else ans=i;
		}
	if(ans<=65536) fout<<ans<<endl;
	else fout<<0<<endl;
}
int main()
{
	init();
	work();
	return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: