题解 | #采药#
采药
https://www.nowcoder.com/practice/d7c03b114f0541dd8e32ce9987326c16
#include <iostream>
#include <algorithm>
using namespace std;
//dp[item][time] = value
int dp[105][2000];
int herdTime[105]; //采草药的时间
int herdValue[105]; //采草药的价值
int main() {
int T, M;
while (scanf("%d%d", &T, &M) != EOF) { // 注意 while 处理多个 case
//由于后面的dp[0][0] 是为0的，所以从1开始方便编程
for(int i = 1; i <= M; i++){
scanf("%d%d", &herdTime[i], &herdValue[i]);
}
for(int item = 0; item <= M; item++){
for(int time = 0; time <= T; time++){
if(0 == item || 0 == time){
dp[item][time] = 0;
continue;
}
if(time - herdTime[item] < 0){ //时间不够采摘,就不采摘了，拿上一次的结果
dp[item][time] = dp[item - 1][time];
}else{ //时间够采摘,就看看到底要不要采，把 采摘的情况 和 不采摘的情况取一个最大值
dp[item][time] = max(dp[item - 1][time], herdValue[item] + dp[item - 1][time - herdTime[item]]);
}
}
}
printf("%d\n", dp[M][T]);
}
}
// 64 位输出请用 printf("%lld")
我觉得这里dp的意思是dp[i][j] 目前可以选的种类是0 - i， 此时的空间还有 j
