$\LARGE\color{orange}{刷题日记(算法提高课)}$

这道题实际上是二维费用的 01 背包问题

在一般的 01 背包里面，我们的花费实际上只有体积，也就是花费是一维的

对于这种花费是二维的题目，处理方式跟一维的完全一样，只不过注意一下字母的表示即可

在这道题里面，花费 1 为精灵球的数量，花费 2 为皮卡丘的体力

我们前者用 $v1$ 表示，后者用 $v2$ 表示

在这里我们直接给出二维 $f[j][k]$ 所表示的集合：在前 $i$ 个物品当中选择，花费 1 不超过 $j$ ，花费 2 不超过 $k$ 的所有选法，属性为所有选法当中收服精灵的数量最多

根据一维费用 01 背包的经验，这里我们很容易便可以得出二维费用的 01 背包的状态转移方程 $f[j][k]=max(f[j][k], f[j-v1][k-v2]+1)$

最后的答案要输出两个，第一个是最大收服的精灵数量，即 $f[V1][V2]$

第二个为收服精灵达到最大时，花费 2 的数值尽可能小，也就是我们需要从最大开始倒着枚举

这道题还有一个细节是，皮卡丘体力为 0 时是不能收服精灵的，因此花费 2 的最大值不能到 $V2$ ，只能到 $V2-1$

完整代码如下：

#include <iostream>

using namespace std;

const int N = 1010;
int f[N][N];
int n, V1, V2;

int main()
{
    cin >> V1 >> V2 >> n;
    for(int i = 1; i <= n; i++)
    {
        int v1, v2;
        cin >> v1 >> v2;
        for(int j = V1; j >= v1; j--)
            for(int k = V2 - 1; k >= v2; k--)
                f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
    }
    cout << f[V1][V2 - 1] << " ";
    int k = V2;
    while(k > 0 && f[V1][k - 1] == f[V1][V2 - 1]) k--;//下一个k满足条件我们才往下跳
    cout << V2 - k << endl;
    return 0;
}

其实这种二维费用的 01 背包问题根本不难，将所有的花费用 $v1,\ v2$ 表示出来之后就很简单了