本文共 2946 字，大约阅读时间需要 9 分钟。

小D和他的魔法石

题目链接：

到牛客看：

题目大意

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

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

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

思路

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

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

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

那考虑怎么才能换出这个局面，怎么才换不出。

但如果 $n$ 是 $2$ 时呢？

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

代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #define ll long longusing 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;}