1292：宠物小精灵之收服（二维费用的01背包问题）

1292：宠物小精灵之收服

• 花费1：精灵球数量，花费2：皮卡丘的体力，价值均为1
• 注意皮卡丘体力小于等于0不能捕捉，要从体力-1开始递推

收服C个小精灵时皮卡丘的剩余体力值最多为R：

• 当我们算出最多收复C个精灵时，最大体力从后往前找，找到需要最小体力的情况,那么剩余体力为m2 - k

    int k = m2 - 1;
    while(k > 0 && f[m1][k - 1] == f[m1][m2 - 1]) k --;
    cout<<m2 - k;

代码如下：

#include<iostream>
#include<algorithm>

using namespace std; 

const int N = 1e3 + 10, M = 510;

int m1,m2,n;
int f[N][M];

int main(){
    cin >> m1 >> m2 >> n;
    for(int i = 1; i <= n; i ++ ) {
        int v1,v2; cin >> v1 >> v2;
        for(int j = m1; j >= v1; j -- ){
            for(int k = m2 - 1; k >= v2; k -- ){
                f[j][k] = max(f[j][k],f[j - v1][k - v2] + 1);
            }
        } 
    }
    cout<<f[m1][m2 - 1]<<" ";
    int k = m2 - 1;
    while(k > 0 && f[m1][k - 1] == f[m1][m2 - 1]) k --;
    cout<<m2 - k;
    return 0; 
}