P1048 [NOIP 2005 普及组] 采药

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T, M;
    cin >> T >> M;
    vector<int> cost(M), value(M);
    for (int i = 0; i < M; i++) cin >> cost[i] >> value[i];

    // dp[j][t]：只考虑前 j 株草药、总耗时不超过 t 时的最大总价值
    vector<vector<int>> dp(M + 1, vector<int>(T + 1, 0));
    for (int j = 1; j <= M; j++) {
        for (int t = 0; t <= T; t++) {
            dp[j][t] = dp[j - 1][t];
            if (t >= cost[j - 1]) dp[j][t] = max(dp[j][t], dp[j - 1][t - cost[j - 1]] + value[j - 1]);
        }
    }

    cout << dp[M][T] << "\n";
    return 0;
}