P1048 [NOIP 2005 普及组] 采药——题解

解题思路

这是标准 0-1 背包。f[j] 表示时间不超过 $j$ 的最大价值。处理每株草药时，从 $T$ 递减枚举容量，使用 f[j]=max(f[j],f[j-time]+value)，倒序保证每株只选一次。

复杂度分析

时间复杂度 $O(TM)$，空间复杂度 $O(T)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int f[1005];
int main(){
    int T,M;cin>>T>>M;
    while(M--){int t,v;cin>>t>>v;for(int j=T;j>=t;j--)f[j]=max(f[j],f[j-t]+v);}
    cout<<f[T]<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; int f[1005]; int main(){ int T,M;cin>>T>>M; while(M--){int t,v;cin>>t>>v;for(int j=T;j>=t;j--)f[j]=max(f[j],f[j-t]+v);} cout<<f[T]<<'\n';return 0; }