A41063. 采药
填空题
困难
知识点
题目描述
采药
题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
输入第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例输入
70 3
71 100
69 1
1 2
样例输出
3
参考答案
#include <iostream>
#include <cstring>
using namespace std;
int main() {
int T = 0; // 规定时间
int M = 0; // 草药数目
cin >> T >> M;
// 用i表示第i个草药，便于理解
int time[M + 1] = { 0 }; // 第i个草药的采集时间
int value[M + 1] = { 0 }; // 第i个草药的价值
for (int i = 1; i < M + 1; i++) {
cin >> time[i] >> value[i];
}
int res[T + 1][M + 1]; // 最优解，表示在时间T内考虑前M个物品时的最大价值
memset(res, 0, sizeof(res)); // 数组归零的写法要用memset()，用res[][] = { 0 }好像不行
for (int i = 1; i < T + 1; i++) {
for (int j = 1; j < M + 1; j++) {
if (i < time[j]) {
res[i][j] = res[i][j - 1]; // 第i个草药没法采
} else {
// 第i个草药可以采，比较采和不采的价值，注意前者的计算公式
res[i][j] = max(res[i][j - 1], res[i - time[j]][j - 1] + value[j]);
}
}
}
cout << res[T][M] << endl; // 输出在T时间内考虑M个草药的最优解
return 0;
}
上一题
下一题