P1616 疯狂的采药.md

P1616 疯狂的采药

题意

给 $n$ 个物品和 $t$ 的时间，可以多次用 $a_i$ 的时间获得 $b_i$ 的价值，问能获得的最大价值。

思路

完全背包模板。

代码

#include <iostream>

#define int long long

using namespace std;

int t, n;
int a[10005];
int b[10005];
int dp[10000005];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = a[i]; j <= t; ++j) {
            dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
        }
    }
    cout << dp[t] << endl;
    return 0;
}