标签：技术   name   net   const   效率   sizeof   src   ring   复杂度   

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

算法1

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

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

时间复杂度

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

C++ 代码

#include 
#include 
#include 
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 = 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  res || (res == f[j][k] && k 

算法2

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

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

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

时间复杂度

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

C++ 代码

#include 
#include 
#include 
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 = d; j--)
            for (int k = K; k >= 1; k--)
                if(f[j - d][k - 1] + c 

运行效率

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

AcWing 1022. 宠物小精灵之收服

标签：技术   name   net   const   效率   sizeof   src   ring   复杂度   

原文地址：https://www.cnblogs.com/dmoransky/p/11563581.html