题解 | 采药

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// “孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。
//我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

//输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。
//接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。

//可能有多组测试数据，对于每组数据， 输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

int main() {
    int T, M;//T表示总时间，M表示总种类
    while (scanf("%d%d", &T, &M) != EOF) {
        int t, v;
        int dp[1001][101];
        vector<int> TotalTime;
        vector<int> Value;
        for (int i = 0; i < M; i++) { //赋值
            scanf("%d%d", &t, &v);
            TotalTime.push_back(t);
            Value.push_back(v);
        }
        //当时间为0
        for (int i = 0; i <= M; i++) {
            dp[0][i] = 0;
        }
        //当采药数为0时
        for (int i = 0; i <= T; i++) {
            dp[i][0] = 0;
        }
        for (int i = 1; i <= T; i++) {
            for (int j = 1; j <= M; j++) {
                if (i - TotalTime[j - 1] < 0) {
                    dp[i][j] = dp[i][j - 1];
                } else {
                    dp[i][j] = max(dp[i][j - 1], dp[i - TotalTime[j - 1]][j - 1] + Value[j - 1]);
                }
            }
        }
        printf("%d\n", dp[T][M]);
    }
    return 0;
}