Luogu 2737 [USACO4.1]麦香牛块Beef McNuggets

NOIP2017 D1T1 的结论，两个数$a, b$所不能表示出的最大的数为$a * b - a - b$。

听了好几遍证明我还是不会

注意到本题中给出的数都非常小，所以最大不能表示出的数$\leq 256 * 256 - 256 * 2 = 65024$。

那么直接用这个$65024$作为背包容量跑完全背包就好了。

时间复杂度$O(maxV * n)$。

Code：

#include <cstdio>

using namespace std;

const int N = ;

const int M = ;

int n, a[N];

bool f[M];

inline void read(int &X) {

    X = ; char ch = ; int op = ;

    for(; ch > ''|| ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

int main() {

    read(n);

    for(int i = ; i <= n; i++) read(a[i]);

    f[] = ;

    for(int i = ; i < M; i++)

        for(int j = ; j <= n; j++)

            if(i - a[j] >= ) f[i] |= f[i - a[j]];

    int ans = ;

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

        if(!f[i]) {

            ans = i;

            break;

        }

    if(ans > ) ans = ;

    printf("%d\n", ans);

    return ;

}

巴特西

Luogu 2737 [USACO4.1]麦香牛块Beef McNuggets

最新文章

热门文章