概览

小智， 皮卡丘
小精灵， 精灵球个数， 皮卡丘的伤害

皮卡丘体力<=0, 伤害的也不能收
用完精灵球

1. 收服尽可能多的精灵
2. 精灵数相同时候，伤害最小

题解

花费1：精灵球数量 N
花费2：皮卡丘体力值 M
价值：小精灵的数量 K

f[i,j,k]表示所有只从前i个物品中选，且花费1不超过j，花费2不超过k的选法的最大价值

老是想着01背包，却没有跳出来从DP的角度直接开始建模问题。问题扩展了，多一维不就可以了吗

f[i,j,k] = max(f[i-1, j, k], f[i-1, j-v1[i], k-v2[i] + 1)

nb!! 注意这里有限制

问：
最多收服的小精灵数 f[K, N, M]
最少耗费体力 f[K, N, m] == f[K, N, M]

真的妙，求数量就这样一下就转化了

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, M = 510;

int n, V1, V2;
int f[N][M];

int main() {
    cin >> V1 >> V2 >> n;

    for (int i = 0; i < n; i ++) {
        int v1, v2;
        cin >> v1 >> v2;
        for (int j = V1; j >= v1; j --)
            for (int k = V2 - 1; k >= v2; k --)
            // 注意体力小于等于0，包括等于0时，小精灵就不会被收服
                f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
    }

    cout << f[V1][V2 - 1] << ' ';
    int k = V2 - 1;
    while ( k > 0 && f[V1][k - 1] == f[V1][V2 - 1]) k --;
    cout << V2 - k << endl;
    return 0;
}