《算法提高课》题解与笔记上线啦!(链接就是这个)
{: style=”color: #FF0000”}
创建时间2024-1-23
$$ #4 1022.宠物小精灵之收服 $$
二维费用背包模型
原题Link
Code:
# include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, M = 5e2 + 10;
int n, m, e;
int f[N][M];
int main(){
scanf("%d %d %d", &n, &m, &e);
for(int i = 1, a, b; i <= e; i ++){ // 边输入边DP
scanf("%d %d", &a, &b);
for(int j = n; j >= a; j --){ // 大于等于精灵球
for(int k = m; k > b; k --){ // 大于体力 (等于0会死)
f[j][k] = max(f[j][k], f[j - a][k - b] + 1); // 个数加一
}
}
}
for(int i = 1; i <= m; i ++){
if(f[n][i] == f[n][m]){ // 实行查找,知道剩余体力
printf("%d %d", f[n][m], m - i + 1);
return 0;
}
}
return 0;
}