P2737 [USACO4.1]麦香牛块Beef McNuggets

  • 13通过
  • 21提交
  • 题目提供者该用户不存在
  • 标签USACO
  • 难度普及+/提高

提交  讨论  题解

最新讨论

  • 暂时没有讨论

题目描述

农夫布朗的奶牛们正在进行斗争,因为它们听说麦当劳正在考虑引进一种新产品:麦香牛块。奶牛们正在想尽一切办法让这种可怕的设想泡汤。奶牛们进行斗争的策略之一是“劣质的包装”。“看,”奶牛们说,“如果你只用一次能装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行: 每个种类包装盒容纳麦香牛块的个数

输出格式:

输出文件只有一行数字:顾客不能用包装盒买到麦香牛块的最大块数或0(如果所有购买方案都能得到满足或者顾客不能买到的块数没有上限)。

输入输出样例

输入样例#1

3

3

6

10

输出样例#1

17

说明

题目翻译来自NOCOW。

USACO Training Section 4.1

分析:数据可以看作是无限的,即使是2,000,000,000,也绝对会超时,如果有个数学方法能够直接算出来就好了,至少要能缩小范围就好了.

如果p,q为自然数,且gcd(p,q) = 1,那么px + qy不能表示的最大数为pq - p - q,这个比较难证明(其实是我不会证明......)在实际做题中,范围可以只取pq,题目中给的最大的正整数为256,但是给出的方法是两个数的,本题会给多个数,我们可以把每两个数的结果算出,发现影响结果的就是最大的两个数,也就是256和255,鉴于数据比较小,取256^2即可,然后就是简单的枚举了,将0~256^2的数试着能不能用给定的数取到,然后从后往前扫描,如果不能取到的数大于256^2,输出0即可.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> int n,a[],vis[]; int main()
{
scanf("%d", &n);
for (int i = ; i <= n; i++)
scanf("%d", &a[i]);
vis[] = ;
for (int i = ; i <= ; i++)
for (int j = ; j <= n; j++)
if (i >= a[j])
if (vis[i - a[j]])
vis[i] = ;
int ans = ;
for (int i = ; i >= ; i--)
{
if (!vis[i])
{
ans = i;
break;
}
}
if (ans > )
ans = ;
printf("%d\n", ans); return ;
}
05-08 08:37