题目描述

blablabla

样例

blablabla

算法1

01背包模型 时间$O(n^3)$，空间$O(n^2)$

采用01背包问题模型。该问题是二维费用的01背包问题，一维是精灵球的数量，另一维是皮卡丘的体力。收益是收服的宠物小精灵个数。

状态表示：$f(u,i,j)$表示仅考虑前$u$个宠物小精灵，最多允许使用的精灵球数是$i$，最多允许消耗的皮卡丘的体力是$j$的前提下，能够收服的宠物小精灵个数的最大值$Max$。

状态方程：$f(u,i,j) = max(f(u-1,i,j), f(u-1,i-v1[u],j-v2[u])+1))$
其中，$v1[i]$是收服第$u$个小精灵所需要消耗的精灵球数量；$v2[i]$是收服第$u$个小精灵所需要消耗的皮卡丘的体力。注意转移的条件是$i >= v1[u] && j > v2[u]$，因为最终皮卡丘的体力不能为零。

同样，第$u$维的状态计算只与第$u-1$维有关，且仅与其左边的状态有关，因此空间上可以优化掉一维，并从大到小计算状态。

最终的状态转移方程是：$f(i,j) = max(f(i,j), f(i-v1[u],j-v2[u])+1))$

时间复杂度

状态有$O(n^3)$，状态计算$O(1)$，整体$O(n^3)$。

参考文献

C++ 代码

#include <iostream>

using namespace std;

const int K = 110, N = 1010, M = 510;   // k是野生宠物小精灵数量，N是精灵球数量，M是皮卡丘体力

int f[N][M];
int v1[K], v2[K];

int main()
{
    int k, n, m;
    cin >> n >> m >> k;

    for (int u = 1; u <= k; u++) cin >> v1[u] >> v2[u];

    for (int u = 1; u <= k; u++) {
        // f(i,j)=max(f(i,j),f(i−v1[u],j−v2[u])+1))
        for (int i = n; i >= v1[u]; i--) {
            for (int j = m; j > v2[u]; j--) {
                f[i][j] = max(f[i][j], f[i-v1[u]][j-v2[u]] + 1);
            }
        }
    }

    int maxNum = f[n][m];
    int minCost = m;
    while (minCost > 0 && f[n][minCost] == maxNum) minCost--;
    int resCost = m - minCost;

    cout << maxNum << ' ' << resCost << endl;

    return 0;
}