USACO 麦香牛块（+ NOIP2017提高组Day1T1）

HigHwind · 2018-02-06 19:58:58 · 题解

哇题目看得我又饿了

原题

题目描述

农夫布朗的奶牛们正在进行斗争，因为它们听说麦当劳正在考虑引进一种新产品：麦香牛块。奶牛们正在想尽一切办法让这种可怕的设想泡汤。奶牛们进行斗争的策略之一是“劣质的包装”。“看，”奶牛们说，“如果你只用一次能装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(如果所有购买方案都能得到满足或者顾客不能买到的块数没有上限)。

输入输出样例

输入样例：

3
3
6
10

输出样例：

17

解答

特殊情形：NOIP2017_Day1 T1 小凯的疑惑

小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在小凯无法准确支付的商品。

若\gcd(a,b)=1，求k_{max}≠ma+nb(k,a,b,m,n\in\Bbb{N_+})

就是说a,b互质，求a,b的自然数倍之和所不能表示出来的最大的数。

据说是小学奥赛题……结论很简单

这题直接输出就好了。

但是直接证明我不会证……

不过证ab-a-b无法被表示还是可以的，用反证法：

不妨假设

则整理得

而据互质条件\gcd(a,b)=1得

可解得m=-1\notin\Bbb{N_+}，故原假设不成立，即ab-a-b不能被表示。

投机取巧

有了上面的这个结论，我们就可以回到本题来了。（别告诉我你已经忘了题目了-。-）

题中给了一个答案范围ans_{max}=2*10^9，不用说，拿这个枚举肯定是Timeout。

那么能不能再缩减一下这个范围呢？

注意题目中我划的高亮数据范围：

1≤i≤256

所以当i=i_{max}=256时，用上面的结论(ab-a-b)可知ans_{max}=256^2-2*256

有了这个上限，我们就只用枚举到ans_{max}了。

当然，还要注意题目要求输出0的时候。

程序

之所以MAXLIM使用了256^2-2*256+1是为了简化下文代码中循环次数的处理。

这个值是可以取的最小值，再往大取是没有问题的，所以我在其他题解里也看到过用70000做的，这个值可能是试出来的吧。

本来这个值取的再小一点也不会有太大问题，但是洛谷给的数据太刁钻了……

4
252
250
254
256

对于这组数据，如果MAXLIM取为256^2-2*256（仅比理想最小值小1），这组数据就会得到65023而不是输出0……好伤啊！

#include <bits/stdc++.h>

#define LL unsigned long long
#define MAXLIM 65025 // = 256^2-2*256 + 1

using namespace std;
int f[MAXLIM + 1]; //f[i]存储整数i能否被表示
int i, j, n;
int a[11];
int main() 
{
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    f[0]=1;

    // 核心代码，背包处理
    for (i=1;i<=n;i++)
        for (j = a[i]; j <= MAXLIM; j++)
            f[j] = f[j] || f[j - a[i]];

    int ans = 0;                  //存结果用
    for (i = MAXLIM; i >= 0; i--) //找不能被表示的最大的数，倒找比顺找好
        if (f[i] == 0)
        {
            ans = i;
            break;
        }
    if (ans>65024)
        ans = 0;
    cout << ans << endl;

    return 0;
}