1 条题解
-
0
【本题解由站长编写】
dp[t] 表示总时间不超过 t 时能得到的最大价值,初始值为 0。每株草药最多采一次,因此按时间倒序转移 dp[t] = max(dp[t], dp[t−cost]+value)。原解释中的“恰好用 t 时间”与初始化不一致,这里采用“不超过 t”的定义。
代码(C++17)
#include <bits/stdc++.h> using namespace std; int main() { int T, M; cin >> T >> M; vector<int> dp(T + 1, 0); for (int i = 0; i < M; i++) { int t, v; cin >> t >> v; for (int j = T; j >= t; j--) dp[j] = max(dp[j], dp[j - t] + v); } cout << *max_element(dp.begin(), dp.end()) << endl; return 0; }
- 1
信息
- ID
- 4256
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者