参考了墨染空同学的解法二写的代码,时间复杂度O(M(K^2))

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1010;
int V1;
int V2;
int f[N][N]; // f[i][j] 是得到精灵数为i体力值为j消耗的最少的精灵球数
int n, m, k;

int main()
{
    scanf("%d%d%d",&n,&m,&k);

    memset(f, 0x3f, sizeof f);

    // 初始化, 精灵数为0消耗的精灵球数肯定为0
    for(int i = 0; i <= m - 1;  i ++)
        f[0][i] = 0;

    for(int i = 0; i < k; i ++)
    {
        cin >> V1 >> V2;
        for(int j = k; j >= 1; j -- )
        {
            for(int g = m - 1; g >= V2; g --)
            {
                // 精灵球数必须在n之内
                if(f[j - 1][g - V2] + V1 <= n)
                    f[j][g] = min(f[j][g], f[j - 1][g - V2] + V1);
            }
        }
    }

    // 最大精灵数
    int res; 
    for(int i = k; i >= 0; i --) 
        if(f[i][m - 1] != INF)
        {
            res = i;
            break;
        }

    // 剩余体力值
    int ans = m - 1;
    // 不同策略,只要精灵球数的消耗在n之内即可,不用和上一种方法一样需要相等才行
    while(ans > 0 && f[res][ans - 1] <= n) ans --;

    cout << res << " " << m - ans << endl;

    // 这是解法一求剩余体力值的方法
    // int res = m - 1;
    // while(res > 0 && f[n][res - 1] == f[n][m - 1]) res --;
    // cout << f[n][m - 1] << " " << m - res << endl;

    return 0;
}