在背包问题中，体积w与价值v是可以互逆的！
可以将\(f[i]\)表示为体积为\(i\)能装的最大价值，
也可以将\(f[i]\)表示为价值为\(i\)所需的最小体积。
两者等价，我们只需要选择范围较小的那维作为体积就可以了！
这直接影响到时空复杂度。
这题就是个案例。

算法1

(体力、精灵球数为费用、精灵数为价值) \(O(nmk)\)

\(f[i][j]\)表示为体力为\(i\)，精灵球数为\(j\)所收集到的最大精灵。

时间复杂度

差不多是\(5 * 10^7\)的级别。

C++ 代码

#include <cstdio>#include <iostream>#include <cstring>using namespace std;const int N = 1005, M = 505, S = 105;int n, m, K, w[S], v[S], f[N][M];int main() { memset(f, 0xcf, sizeof f); scanf("%d%d%d", &n, &m, &K); for(int i = 1; i <= K; i++) scanf("%d%d", w + i, v + i); f[0][0] = 0; for(int i = 1; i <= K; i++) { for(int j = n; j >= w[i]; j--) for(int k = m; k >= v[i]; k--) f[j][k] = max(f[j][k], f[j - w[i]][k - v[i]] + 1); } int res = -1, t; for(int j = 0; j <= n; j++) { for(int k = 0; k <= m; k++) { if(f[j][k] > res || (res == f[j][k] && k < t)) { res = f[j][k], t = k; } } } printf("%d %d\n", res, m - t); return 0;}

算法2

发现\(k\)很小，于是就...

(体力、精灵数为费用，精灵球数为价值) \(O(k^2m)\)

\(f[i][j]\) 表示体力为 \(i\), 收集了 \(j\)个 精灵 用的最小的精灵球数量

时间复杂度

大概是\(5 * 10 ^ 6\)的级别。

C++ 代码

#include <cstdio>#include <iostream>#include <cstring>using namespace std;const int N = 1005, M = 505, S = 105;const int INF = 0x3f3f3f3f;int n, m, K, f[M][S];int main() { memset(f, 0x3f, sizeof f); scanf("%d%d%d", &n, &m, &K); f[0][0] = 0; for (int i = 1, c, d; i <= K; i++) { scanf("%d%d", &c, &d); for (int j = m; j >= d; j--) for (int k = K; k >= 1; k--) if(f[j - d][k - 1] + c <= n) f[j][k] = min(f[j][k], f[j - d][k - 1] + c); } for (int k = K; ~k; k--) { int p = INF; for (int j = 0; j <= m; j++) { if(f[j][k] != INF && j < p) p = j; } if(p != INF) { printf("%d %d\n", k, m - p); return 0; } } return 0;}

运行效率

这题启示我们，要用灵活的思维去考虑问题\(qwq\)