题解 | #采药#

#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