1174: 【USACO】麦香牛肉
时间限制: 1 Sec 内存限制: 16 MB
提交: 115 解决: 67
[提交][状态][讨论版]题目描述
农 夫约翰的奶牛几乎要武装暴动，因为他们听说麦当劳要推出新产品麦香牛肉。奶牛们要尽力阻止这种产品的上市。他们研究了一种“劣等包装”策略。奶牛们说： “如果麦香牛肉有3块，6块以及10块装这三种，那么想买 1, 2, 4, 5, 7, 8, 11, 14, 或17块牛肉的顾客就得不到满足了。劣等的包装，劣等的产品！” 帮助奶牛们。给出N (不同包装的种类数, 1 <= N <= 10)，以及N个正整数 (1 <= i <= 256)表示每种包装中牛肉数量，输出最大的不能买到的牛肉数量。如果任何消费要求都可以被满足或不能满足的牛肉数量没有上界，则输出0。最大的可能值 （如果存在）不超过2,000,000,000。
输入
第1行: N 第2..N+1行: 一个盒子里的牛肉数量。
输出
输出题目中要求的单个整数。
样例输入
3 3 6 10
样例输出
17
提示
来源
题解：
n=1 输出0
n个整数最大公约数不为1 输出0
逻辑动归：f[i]={f[i-a[j]||f[i]}, 0=<j<n,i>a[j] ，i不超过两个数的最小公倍数，应该小于256*256。
code
#include<fstream>
#include<algorithm>
using namespace std;
const int N(70000);
int n,a[15];
bool f[N];
ifstream cin("nuggets.in");
ofstream cout("nuggets.out");
int gcd(int x,int y)
{
int z;
for (z=x%y;z;x=y,y=z,z=x%y);
return y;
}
bool possible()
{
if (n==1) return false;
int t=a[0];
for (int i=1;i<n;i++) t=gcd(t,a[i]);
if (t==1) return true;
else return false;
}
void solve()
{
fill(f,f+N,false);
for (int i=0;i<n;i++) f[a[i]]=true;
for (int i=1;i<N;i++)
{
for (int j=0;j<n;j++)
if (a[j]<=i)
if (f[i-a[j]])
{
f[i]=true;
break;
}
}
for (int i=N-1;i>0;i--)
if (!f[i])
{
cout<<i<<endl;
break;
}
}
int main()
{
cin>>n;
for (int i=0;i<n;i++) cin>>a[i];
if (!possible()) cout<<0<<endl;
else solve();
return 0;
}posted on 2012-09-09 19:31
龙在江湖 阅读(460)
评论(0) 编辑 收藏 引用 所属分类:
动态规划 、
数论 、
竞赛题解_USACO