答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">// C++代码1
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Pokemon {
int ballsNeeded;
int damage;
};
bool sortByDamage(const Pokemon& p1, const Pokemon& p2) {
return p1.damage < p2.damage;
}
int main() {
int N, M, K;
cin >> N >> M >> K;
vector<Pokemon> pokemons;
for (int i = 0; i < K; i++) {
int balls, damage;
cin >> balls >> damage;
pokemons.push_back({balls, damage});
}
sort(pokemons.begin(), pokemons.end(), sortByDamage);
int maxCaught = 0;
int maxRemainingHP = M;
int currentBalls = N;
int currentHP = M;
for (int i = 0; i < K; i++) {
int balls = pokemons[i].ballsNeeded;
int damage = pokemons[i].damage;
if (currentHP <= damage) {
break;
}
int maxPossibleCaught = min(currentBalls / balls, (currentHP - 1) / damage);
if (maxPossibleCaught > maxCaught) {
maxCaught = maxPossibleCaught;
maxRemainingHP = currentHP - maxCaught * damage;
}
currentHP -= damage;
currentBalls -= balls;
}
cout << maxCaught << " " << maxRemainingHP << endl;
return 0;
}</pre><pre class="brush:cpp;toolbar:false">// C++代码2
#include <bits/stdc++.h>
#define N 5000
using namespace std;
int f[N][N];
int n, m, k;
int a[N], b[N], c[N];
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= k; i++) {
cin >> a[i] >> b[i];
}
for (int i = 1; i <= k; i++) {
for (int j = n; j >= a[i]; j--) {
for (int l = m; l >= b[i]; l--)
f[j][l] = max(f[j][l], f[j - a[i]][l - b[i]] + 1);
}
}
int ans;
for (ans = 0; ans <= m; ans++) {
if (f[n][ans] == f[n][m])
break;
}
printf("%d %d\n", f[n][m], m - ans);
return 0;
}</pre><pre class="brush:cpp;toolbar:false">// C语言参考代码
#include <stdio.h>
#include <stdlib.h>
#define N 5000
int f[N][N];
int n, m, k;
int a[N], b[N], c[N];
int max(int a, int b) {
return (a > b) ? a : b;
}
int main() {
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= k; i++) {
scanf("%d %d", &a[i], &b[i]);
}
for (int i = 1; i <= k; i++) {
for (int j = n; j >= a[i]; j--) {
for (int l = m; l >= b[i]; l--) {
f[j][l] = max(f[j][l], f[j - a[i]][l - b[i]] + 1);
}
}
}
int ans;
for (ans = 0; ans <= m; ans++) {
if (f[n][ans] == f[n][m])
break;
}
printf("%d %d\n", f[n][m], m - ans);
return 0;
}</pre>
这道题暂未补解析。