[NOIP 2005 普及组] 采药

知识点

动态规划、01背包

解题思路

dp[t]表示限时t内的最大价值。每种草药耗时w、价值v，按时间倒序更新dp[t]=max(dp[t],dp[t-w]+v)。输出dp[T]。

正确性说明

任何最优方案对当前草药都只有不选、选一次两类；选择时剩余方案不含当前草药。倒序更新保留上一层状态，恰好实现这两类的最大值，逐物品归纳即正确。

易错点

不能正序遍历重复采同一株；耗时超过剩余容量时不能选择；每株的时间、价值都不是重量比贪心。

复杂度

时间O(TM)，空间O(T)。

参考代码（GNU C++17）

#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>dp(T+1);while(M--){int w,v;cin>>w>>v;for(int t=T;t>=w;t--)dp[t]=max(dp[t],dp[t-w]+v);}cout<<dp[T]<<'\n';}