宠物小精灵之收服 https://www.acwing.com/problem/content/1024/

二维费用流背包

花费1 - 精灵球数量
花费2 - 皮卡丘体力值
价值 - 小精灵数量

状态表示
集合 - f[i][j][k]表示所有只从前i个物品中选，且花费1不超过j，花费2不超过k的选法
属性 - Max

状态计算
f[i][j][k] = max(f[i-1][j][k], f[i-1][j-v1[i]][k-v2[i]] + 1); 每个物品价值为1
N - 精灵球数量 M - 皮卡丘初始体力 K - 野生小精灵数量
最多收服小精灵数量 f[K][N][M]
最少耗费体力，求m使得 f[K][N][m] == f[K][N][M] 且m最小

#include <iostream>
using namespace std;

const int N = 1010, M = 510;
int V1, V2, n;
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的精灵不能被收服，从V2-1开始
                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;
    return 0;
}