P2737 [USACO4.1]麦香牛块Beef McNuggets 数学题 + 放缩思想

https://www.luogu.org/problem/show?pid=2737#sub

先说一个结论：对于两个数p, q，且gcd(p, q) = 1（这个很重要，是条件来的）。他们不能组合成的最大的数字是pq - p - q

任何大于pq - p - q的数字，都能组合得到。

那么，题目中无法组合得到的最大的数字，也就是最后输出的答案，最大也只是256 * 255 - 256 - 255 = 64769

注意到题目还要求，"不存在不能买到块数的上限，则输出0"，什么意思呢？也就是，只有一个数字3，那么你所有2的倍数都是无法组合成的了，这个时候输出0.

那么我们既然已经知道最后的答案最大也只是64769，所以可以暴力dp，

那么如果最后得到不能组合成的数字大于64769，则说明是：没有上限。也就是只有一个3、或者是两个数字：3、6这样的情况。

要注意数字3和6是不能套用上面的公式的，因为她们不互质。

但是这题最坏的情况，上限也只是64769，也就是说如果出现了255、256这一对数字，64769以上的数字是可以组合成的了。

那么完全背包dp[100000]，dp[val] = true表示这个数字能组合成。最后统计下那个最大的数字不能组合成。

如果这个数字 > 64769，则说明不存在上限。

但是会不会是那个数字val = 100001不能组合成，前面的都能组合成呢？我还没得得到证明。

意思就是，会不会最后得到不能组合的数字是100001，这个时候应该是无解的。如果存在这样的情况，那么我的dp数组开得就不够大了。

1、如果存在这样的情况，那么说明那n个数字中，任意两个都不互质。因为如果是互质的，不能表达的最大的数字只是64769，后面的数字肯定能表达。

2、既然她们不互质，设任意一个数是k，（1 <= k <= 256），如果100001不能组合成，那么100001 - k也不能组合成。

100001 - 2k也不能组合成。那么，k最大也就256，最后还是会落在100000之下。所以dp数组是够大的。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int maxn =  + ;

int dp[maxn], DFN = ;

int n;

void work() {

    DFN++;

    dp[] = DFN;

    for (int i = ; i <= n; ++i) {

        int val;

        cin >> val;

        for (int j = val; j <= maxn - ; ++j) {

            if (dp[j - val] == DFN) dp[j] = DFN;

        }

    }

    int ans = ;

    for (int i = maxn - ; i >= ; --i) {

        if (dp[i] != DFN) {

            ans = i;

            break;

        }

    }

    if (ans > ) ans = ;

    cout << ans << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    while (cin >> n) work();

    return ;

}

巴特西

P2737 [USACO4.1]麦香牛块Beef McNuggets 数学题 + 放缩思想

最新文章

热门文章