AcWing 1022. 宠物小精灵之收服
原题链接
简单
二维费用的背包问题
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10, M = 1e3 + 10, K = 5e2 + 10;
int n, m, k;
int v1[N], v2[N];
int f[M][K]; // f[i][j][k]:从前 i 个物品选 体积1不超过 j 体积2不超过 k 的情况下的最大值
int main() {
scanf("%d%d%d", &m, &k, &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &v1[i], &v2[i]);
for (int i = 1; i <= n; i++)
for (int j = m; j >= v1[i]; j--)
for (int a = k; a >= v2[i]; a--)
f[j][a] = max(f[j][a], f[j - v1[i]][a - v2[i]] + 1);
// 若 f[m][k] != f[m][k - 1] 则说明当前的最大值一定是恰好耗尽了体力所得
// 而题目要求当体力为 0 时不可收服 则当前实际最大值应该是 f[m][k - 1]
// int c = f[m][k] == f[m][k - 1] ? f[m][k] : f[m][k - 1];
int c = f[m][k - 1]; // 也可以直接写
int r = 1e9;
for (int i = 0; i <= k; i++)
if (f[m][i] == c) r = min(r, i);
r = k - r;
printf("%d %d", c, r);
return 0;
}