算法1

时间复杂度 $O(NMK)$

C++ 代码

#include <iostream>
using namespace std;

const int N = 1010, N1 = 501, N2 = 101;
int n, m, k;
int a, b;
int f[N][N1];

/*

状态表示f[i,j,l]
    集合：在前i个小精灵中选，且所用精灵球数量不大于j时，所花费体力值不大于l时收服的小精灵数量的集合
    属性：求最大值，取max()
            首先是收服小精灵数量最多，之后才是剩余体力值最多
状态计算：
    f[i-1,j,l]表示不收服第i个小精灵，共收服多少小精灵
    f[i-1,j-a,l-b]+1表示收服第i个小精灵后共收服多少小精灵

*/

/*
收服结束后，皮卡丘体力值不能为0
故遍历到m-1代表不减到0的遍历到m
*/
int main()
{
    cin >> n >> m >> k;

    for(int i=1; i<=k; i++)
    {
        cin >> a >> b;
        for(int j=n; j>=a; j--)
            for(int l=m-1; l>=b; l--)
                f[j][l] = max(f[j-a][l-b]+1, f[j][l]);
    }

    int minPower = 0;

    for(int i=1; i<=m-1; i++)
    {
        if(f[n][m-1] == 0)
            break;
        if(f[n][m-1] == f[n][i])
        {
            minPower = i;
            break;
        }
    }

    cout << f[n][m-1] << ' ' << m-minPower;

    return 0;
}

算法2

时间复杂度 $O(KKM)$

快了一个数量级

参考文献

https://www.acwing.com/solution/content/4640/