洛谷 P1616 - 疯狂的采药

题目描述

P1616 疯狂的采药

解法：完全背包问题

#include <bits/stdc++.h>
using namespace std;const int maxm = 10010, maxt = 10000010;
long long v[maxm], t[maxm], dp[maxt];
int main(){
    int T , M;cin >> T >> M;for(int i = 1;i <= M ;i ++) cin >> t[i] >> v[i];for(int i = 1;i <= M;i ++){
    for(int j = t[i];j <= T;j ++){
    dp[j] = max(dp[j],dp[j - t[i]] + v[i]);}}cout << dp[T];
}