三维DP 利用循环遍历从右至左 优化掉第一维 剩下的就是枚举dp数组使得消耗的体力最小的同时仍然能取得最大的宠物捕获量 枚举到了立即输出答案

#include<bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int n,m,k;
int main()
{
    cin >> n >> m >> k;
    m--;
    for(int i = 0; i < k; i++)
    {
        int hp, count;
        cin >> count >> hp;
        for(int j = m; j >= hp; j--)
        {
            for(int k = n; k >= count; k--)
                dp[j][k] = max(dp[j][k], dp[j-hp][k-count] + 1);
        }
    }
    for(int i = 0; i <= m; i++)
        if(dp[i][n] == dp[m][n])
            return cout << dp[m][n] << " " << m + 1 - i, 0;
    return 0;
}