小D和他的魔法石

题目链接：nowcoder 214271

到主站看：https://blog.csdn.net/weixin_43346722/article/details/112727063

题目大意

有一些魔法石，每种有无限个，用一个耗费一个值的体力，获得一个值的能力。

然后你可以有 k 次机会把两种魔法石的体力值互换，一定要把 k 次都用完。

然后问你在耗费体力不大于 m 的时候，最多能有多少能力值。

思路

这道题主要是考虑分类讨论。

首先，很明显的就是如果 ，我们就直接做完全背包。

那考虑有换的机会，我们可以想到贪心。让一个魔法石耗费体力值最小，获得能力值最大。

那考虑怎么才能换出这个局面，怎么才换不出。
我们可以发现，k 就算是 ，也可以换出。

但如果 是 时呢？
因为交换次数一定要用完，那我们就要判断换完之后是否是最优的。
是最优的就按这个输出，否则就又是背包。

那对于 不是 的情况，那一定可以构造最优的石头。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long

using namespace std;

int n, m, k, a[1001], b[1001], times;

int main() {
    scanf("%d %d %d", &n, &m, &k);

    if (k == 0) {//不能变换，那就是一道普通的背包
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++) scanf("%d", &b[i]);

        ll f[2][1001], ans = 0;
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n; i++)
            for (int j = m; j >= 0; j--) {
                f[i & 1][j] = f[(i - 1) & 1][j];
                times = 1;
                while (j - a[i] * times >= 0) {
                    f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - a[i] * times] + b[i] * times);
                    times++;
                }
            }

        for (int i = 0; i <= m; i++)
            ans = max(ans, f[n & 1][i]);

        printf("%lld", ans);

        return 0;
    }

    if (n == 2) {//只有两种魔法石
        int maxn = 0, minn = 2147483647;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            minn = min(minn, a[i]);
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &b[i]);
            maxn = max(maxn, b[i]);
        }
        if ((a[1] == minn && b[1] != maxn) || (a[1] != minn && b[1] == maxn)) {//原本不是最优
            if (k & 1) {//能在用完交换次数后达到我们要的最优状态
                printf("%lld", 1ll * maxn * (1ll * (m / minn)));

                return 0;
            }
            else {//不能，那就是背包
                ll f[2][1001], ans = 0;
                memset(f, 0, sizeof(f));
                for (int i = 1; i <= n; i++)
                    for (int j = m; j >= 0; j--) {
                        f[i & 1][j] = f[(i - 1) & 1][j];
                        times = 1;
                        while (j - a[i] * times >= 0) {
                            f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - a[i] * times] + b[i] * times);
                            times++;
                        }
                    }

                for (int i = 0; i <= m; i++)
                    ans = max(ans, f[n & 1][i]);

                printf("%lld", ans);

                return 0;
            }
        }
        else {//原本是最优
            if (k & 1) {//不能
                swap(a[1], a[2]);
                ll f[2][1001], ans = 0;
                memset(f, 0, sizeof(f));
                for (int i = 1; i <= n; i++)
                    for (int j = m; j >= 0; j--) {
                        f[i & 1][j] = f[(i - 1) & 1][j];
                        times = 1;
                        while (j - a[i] * times >= 0) {
                            f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - a[i] * times] + b[i] * times);
                            times++;
                        }
                    }

                for (int i = 0; i <= m; i++)
                    ans = max(ans, f[n & 1][i]);

                printf("%lld", ans);

                return 0;
            }
            else {//能
                printf("%lld", 1ll * maxn * (1ll * (m / minn)));

                return 0;
            }
        }

        return 0;
    }

    int maxn = 0, minn = 2147483647;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        minn = min(minn, a[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
        maxn = max(maxn, b[i]);
    }

    printf("%lld", 1ll * maxn * (1ll * (m / minn)));

    return 0;
}